关于简单DP的理解

---

动态规划思想：同一件事情不做第二次

划分为子问题

塔形问题从最底下往上面推

---

举个栗子(题目来源：杭电OJ)

最重要的就是找出状态转移方程

此题就是从底往上递推，状态转移方程是：

dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]

我们用两个循环套住状态转移方程：

for(int i=n-1;i>=1;i–){

for(int j =1;j<=I;j++){

dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];

}

}

我们提前已经将塔的最后一行元素赋给了dp数组，所以状态转移方程中出现了i+1,j+1;以n-1行为例，上面代码的意思是比较n-1行每个元素下面连接的两个元素大小再加自己就是n-1行这个元素位置上的最优解了（如元素2，就是比较2下面的19和7的大小，可见19比7大，所以确定n-1行第一个元素的最优解为2+19=21），以此类推就知道了n-1行每个元素的最优解了，然后第n行就没有意义了，我们就可以不考虑了，再把我们刚刚求出的n-1行看作**“最后一行”**，这样我们就可以求n-2行的最优解了，以此类推求到第一行，dp[1][1]就是我们要求的最终的最优解。

​ 做一些dp题时或者其它类似斐波那契数列这种需要反复计算同一个数值的问题时（很耗费时间O(2^n)），可以用记忆化搜索的方法，提前算好储存起来，或者边算便储存，保证不重复计算同一个值，再用的时候调用即可。

​ 以上仅为我学简单DP后一点简单的感想和总结，一点拙见，有问题和建议可以通过邮箱联系我，我会虚心接受各位大佬的宝贵意见。