一、 DP介绍： 动态规划与分治方法相似，都是通过组合子问题来求解原问题 的解。与之相反，动态规划应用于子问题重叠的情况，即不同子问题具有公共子问题。而分治方法处理的是互不相同的子问题，递归求解子问题再将它们组合起来。 动态规划有两个性质：1.子问题重叠（相同子问题求解很多次）2.最优子结构。 二、求解DP问题的主要步骤： - 构造最优子结构：刻画一个最优解的结构特征； - 递归定义最优解的值：找到一个递归的求解方案； - 计算最优解的值，通常采用自底向上的方法； - 重构最优解； 三、常见的DP算法： 1、装配线调度问题：
构造最优子结构：问题主要是求解站台最快出站，这样问题中包含两个子问题从S1,j 最快出站和从S2,j 最快出站。每个子问题又包含从站 S1,j-1 或 S2,j-1 最快出站，这样基本可以得出问题的最优子结构。一个递归求解方案：令 fi[j] 为从站 Si,j 出站的最短时间(按照问题最优子结构性质，这是最优解的值)，可以得：
计算最优代价： 采用了自底向上的方法求出最优代价。
构造最优解： 递归的输出最优解的值。 2、矩阵链乘 目标给定矩阵链给定矩阵链 A1,A2,…,An，确定最优的矩阵相乘顺序。
构造最优子结构： 从问题可以看出如果问题规模n = 1 无需求解。若问题规模n > 1现在对问题进行括号化，对于A1,A2,…,An， 我们得在Ak和Ak+1之间加上一个括号使得分开的两个子矩阵链乘积最小，在分别对两个子问题找到最优的划分结果。这样就可以定义构造出最优的子结构。求一个递归解决方案：定义 m[i,j] 为计算矩阵链Ai..j 的乘积所需的最少标量乘法次数。则Mi,j = Mi,k + Mi,k+1 + Pi-1PkPk。计算最优代价： 我们采用了自底向上的方法来求解最优解，在求解过程中用一个辅助的数组S[1….n-1,2….n]来记录最优值m[i，j]对应的分割点K，这样能够构造出最优解。
重构最优解： 借助辅助数组递归的输出最优解的值。
3、最长公共子序列（LCS）：
构造最优子结构：我们可以这样的来求解两个序列的最长公共子序列，若两个子序列X[1…m]和Y[1…n]最后一个元素相同，则我们可以考虑X[1…m-1]和Y[1…n-1]两个子序列的最长公共子序列，若不相同我们可以求解X[1…m-1]和Y[1…n]或者X[1…m-1]和Y[1…n]两个子序列的最长公共子序列，这样我们将问题都推到了子问题的层次上。
一个递归解：我们令C[i,j]为 的LCS的长度，如果i=0或者j = 0则LCS=0，则根据LCS的最优子结构特征我们可以构造出： 计算最优代价：根据递归式，我们能写出一个递归算法来计算最长公共子序列，由于LCS的子问题过多，所以我们采用自底向上的计算。在这个过程中，我们需要借组一个数组b[i,j]来记录最优解得构造过程。构造LCS：我们可以利用b[i,j]所记录的元素来输出最优解。4、最大子段和 给定 n 个整数（可能但不全为负）a1,a2,…,an, 求i, j，使 ai 到 aj 的和最大。
构造最优子结构：在构造这个的时候，我们发现无论从中间还是从两边掐一段都无法正确的定义出问题的最优子结构。我们定义b[j]=max(sum(i:j))，为从i到j子段的最大子段和。我们比较b[j-1]+a[j]和a[j]的大小,如果b[j-1]<0,显然b[j-1]不是最大子段，此时b[j]=a[j]。反之，我们令b[j-1] + a[j] = b[j],找出最大的子段和。一个递归解：由上面构造出的最优子结构我们可以得出一个递归的公式： b[j]=max( b[j-1]+a[j], a[j] ), 1<=j<=n计算最大子段和：由上面的递归公式我们可以写出一个自底向上的递归算法，在算法中我们借助一个变量sum来记录过程中的最大子段和，若此时的b[j]>sum，更新sum中的值，反之，继续求解。直到程序进行完毕。构造最优解：输出sum中的最大子段和。四、 DP的求解方法比较：
自底向上的求解方法： 在用这种方法时一般需要恰当的定义子问题的规模，使得任何子问题都只依赖于更小的子问题的求解。我们可以将问题的规模按照由大到小排列依次求解。每个子问题都只求解一次。
自顶向下带备忘录的的求解方法：动态规划有一个性质为子问题重叠性质，就是对于子问题在递归过程中不断求解，最然问题规模很小，但是求解次数会非常多，造成程序运行非常慢。在使用自顶向下的求解过程中，我们一般要设计一个备忘录，在递归求解过程中对于已经求解过的问题保存在备忘录中，当下次要使用时直接拿出来，不用再次求解。
各自的优缺点：自顶向下只需要求解问题需要的解，不需要对所有子问题都去求解。但是它需要额外的递归开销。自底向上必须对所有子问题进行求解但是可有效减少计算时间和所需的存储空间。 五、 DP与贪心算法的比较： 贪心算法与动态优化问题都应用了最优子结构的性质。在解决动态规划问题时，我们往往需要定义两个或两个以上的子问题去求解比较得到最优的解。而在应用贪心算法时我们应用贪心选择性质，使得选择后问题只留下了一个子问题。这是与动态规划问题的一个很大不同。往往我们可以对一个动态规划问题设计一个贪心算法，也可能对一个贪心问题设计一个DP算法，但是并不是所有的动态规划都能设计成贪心算法。比如，我们在求解0-1背包问题时，我们并不能用贪心算法来求解一个最有解，我们只能通过动态规划问题来设计一个求解方案。总体来说贪心算法和动态规划之间的差别是非常小的。 动态规划方法是一种常用的方法在解决实际问题的时候，对于具有最优子结构和子问题重叠性质的问题我们都能够通过4个步骤来设计一个动态规划的求解方案，对于某些问题我们还可能通过贪心算法来求得子问题的最优解。