动态规划有两个重要因素：最优子结构和重叠子问题。

一般求解步骤：

证明最优子结构性，写出状态方程，自底向上求解，重构解。

下面就我遇到的题目进行总结

1.一维dp[]问题汇总

a.最大连续子序列和

以dp[i]表示第i个数字结尾的最大连续子序列和。看dp[i]和dp[i-1]的关系如果dp[i-1]>0,显然dp[i]=A[i]+dp[i-1],反之dp[i]=A[i]

b.最长不下降子序列

以dp[i]表示以i结尾的最长不下降子序列长度。dp[i]的关系是和前面的dp[1…i-1]均有关系，不能仅由dp[i-1]决定，应该遍历一下前面，找出最大值max（dp[k]+1 or 1）k从0到i-1，是否加1由A[i]与A[k]比较为好

c.DAG最长路

问题对照关键路径吧。

用dp[i]表示从i出发的最长路径，设点i能够到达点k，则dp[i]=max(dp[k]+w),w为i到j的权值。

这个问题有个深思的地方，显然需要先更新dp[k]再来更新dp[i],类似于逆拓扑排序，我们需要拓扑排序吗？正常来说我们是自底向上推导，但是这一次底好像是顶，如果直接自顶向下（递归）就可行了。

d.钢条切割问题

以dp[i]表示i米长钢条的最大价值。设其有一段为k米，则dp[i]=max(dp[i-k]+Pk)

2.二维dp[][]问题

a.最长回文子串

用dp[i][j]表示从i到j是否是最长回文子串，如果A[i]=A[j],显然只要看dp[i+1][j-1]是不是即可。然后长度即为len=j-i+1；

二维问题特别注意更新，自底向上的方法显然先更新长度为1

的再更新长度为2的如此下去。

b.最长公共子序列

用dp[i][j]表示A数组前i个，B数组前j个的最长公共子序列大小。那现在考虑dp[i][j]与什么有关，如果A[i]=B[j],显然dp[i][j]=dp[i-1][j-1]+1，不等的话就与dp[i][j-1]和dp[i-1][j]比较取大值

更新问题正常双重循环

c.矩阵链问题

用dp[i][j]表示从i到j矩阵的最小划分计算量。那现在考虑dp[i][j]与什么有关，不妨假设最后一次划分以k结点为中间点则dp[i][j]=min(dp[i][k]+dp[k+1][j]+Pijk）

更新是由短到长（同回文子串一样）

d.最优二叉检索树

有dp[i][j]表示从i到j构建二叉树的最小期望。那现在考虑dp[i][j]与什么有关，考虑以中间点k为根结点，则dp[i][j]=min(dp[i][k]+dp[k+1][j]+w），w为i到k的概率和。

更新方式为长度更新

e背包问题

背包问题有01背包和完全背包和分数背包之分，分别适用于动态规划、动态规划和贪心算法。

其中01背包和完全背包的空间可以用滚动数组来代替，特别注意01背包的更新。

不妨以dp[i][j]表示前i个物体重量为j的最大收益。则dp[i][j]=max(dp[i-1][j-wi]+pi,dp[i-1][j]),由于第i层只是与第i-1层的状态有关，所以可以简化成为一维滚动数组。

f.Bellman算法

dp[i][j]表示历经i条边的最短路径

循环更新

g.floyd算法

dp[i][j] (k)表示经历前k个点i到j的最短路径

循环更新

3.状态压缩问题

a二维数组取最大数组子块问题

有点类似于最大连续子序列和的二维版。

这里需要将矩阵进行行压缩或者列压缩，压缩为一维矩阵后再利用最大连续子序列和的方法求最值。

b炮兵阵地

利用二进制数来表示每一行的状态

总结：状态压缩类型的dp算比较难的姑且不论，为一维二维进行总结。

第一步设dp： 一维中dp[i]经常表示前i，值为i，以i开始、以i结尾的XXX（问题描述）；二维显然可以用一维的来搭配，比如从i到j，前i前j，前i值为j等

第二步思考状态转移方程： 既是需要讨论一下dp[i]或dp[i][j]=?一般讨论分为单个讨论，遍历讨论。单个讨论是dp[i]仅和dp[i-1]、dp[i-2]有关；遍历讨论是讨论dp[1…i-1],或者讨论k为i到j的某个中间点

第三步思考更新方式： 一维更新基本就自底向上，自顶向下两种；二维更新可以有循环更新，也可以有长度更新，一般来说从i到j类问题基本是长度更新，前i个问题基本是循环更新，只是注意循环有正向和逆向

第四步思考重构解： 这个步骤这里先不赘述

实际上基本12步是连起来的，只要12可行思考方法也就趋于正确。