【code】动态规划

了解动态规划

• 动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等
• 求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。需要你熟练掌握递归思维，只有列出正确的「状态转移方程」，才能正确地穷举
• 动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果
  • 需要判断算法问题是否具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值
  • 动态规划问题存在「重叠子问题」，如果暴力穷举的话效率会很低，所以需要你使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

动态规划的解题方式

• 动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。
• 使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量
• 动态规划与状态和选择有关

动态规划的三要素

• 重叠子问题
• 最优子结构
• 状态转移方程

ps： 用空间换时间是降低时间复杂度的不二法门

原文地址：http://www.cnblogs.com/xiaoyu-jane/p/16894824.html