【你问我答】如何理解动态规划？

动态规划 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 基本思想 若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。 分治与动态规划 共同点：二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解. 不同点：分治法将分解后的子问题看成相互独立的，通过用递归来做。动态规划将分解后的子问题理解为相互间有联系,有重叠部分，需要记忆，通常用迭代来做。 问题特征 最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。 重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。 步骤 描述最优解的结构 递归定义最优解的值 按自底向上的方式计算最优解的值 由计算出的结果构造一个最优解 注意需要需要二维数组用容器

    动态规划是运筹学的一个分支，是求解决策过程的最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。在各种算法中，我认为动态规划是较难掌握好的，主要难在模型的建立。 解题的一般步骤是：     1.找出最优解的性质，刻画其结构特征和最优子结构特征；     2.递归地定义最优值，刻画原问题解与子问题解间的关系；     3.以自底向上的方式计算出各个子问题、原问题的最优值，并避免子问题的重复计算；     4.根据计算最优值时得到的信息，构造最优解。 再推荐一些经典题可以更有效的理解和学习：     1.矩阵连乘 POJ1651     2.走金字塔 POJ1163     3.最长公共子序列(LCS) POJ1458     4.最长递增子序列(LIS)  POJ2533     5.最大子段和 POJ2593 POJ1050     6.凸多边形最优三角剖分      7.背包问题（零一背包，完全背包，部分背包） 建议看背包九讲     8.最优二叉搜索树     9.双调欧几里得旅行商问题 POJ2677

马克

先写出暴力递归, 然后填dp格子,  先把递归结束条件填上去 然后慢慢填完

Mark

Mark

先写出暴力递归的方法，递归调用时，问题规模从n开始逐渐减少，直到减至递归结束的条件。譬如递归结束的边界条件是n=1，那么n=1时就不会继续调用了。 动态规划的方法则是从边界条件开始，问题规模逐渐增加，填dp[i][j]的时候，是假定dp[0~i-1][0~j-1]已经填好了的情况。这个动态规划公式怎么写，可以根据暴力递归转化过来。

考虑对于一个问题写出其可能的状态，把每个状态看做一个节点，对于状态转移在整个图上一定是有向无环图，比如A状态由B状态推导，B状态由C状态推导，C状态又由A状态推导，这样就会造成操作系统里的死锁状态，所以是不行的，一定是A状态由A1,A2,..,An若干个子状态推导而来，而子状态无需考虑如何得到，所以状态转移一定是一个阶段一个阶段的，另外就是，动态规划的题目的数据范围往往不大，不然的话如果不使用滚动数组空间复杂度就会爆炸，所以有时候根据数据范围就能猜测题目是贪心，二分还是DP

动态规划（Dynamic Programming） 动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。   区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。   其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。   即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。 与「分治策略」「动态规划」概念接近的还有「贪心算法」「回溯算法」，由于篇幅限制，程序员小吴就不在这进行展开，在后续的文章中将分别详细的介绍「贪心算法」、「回溯算法」、「分治算法」，敬请关注：） 将「动态规划」的概念关键点抽离出来描述就是这样的： 1.动态规划法试图只解决每个子问题一次 2.一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。