一、DP定义
动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
二、区别
-
贪心处理的问题是：后一阶段的最优状态依赖于前一阶段的一个最优状态。
-
暴力搜索处理的问题是：后一阶段的最优状态依赖于前一阶段的多个状态，但和更之前的状态没关系；状态没重叠。
三、理解
解决DP问题的核心是找到最优子结构，这种结构可以把次优的路径否决掉，重叠状态是否决掉这些次优路径的一个结果。
找到最优子结构->把次优的路径否决掉->重叠状态保存->复杂度k^n变kn。
四、什么问题可以用DP？
首先能状态合并/有状态转移方程才行。每个问题的状态转移方程都不一样。
如果问题本身没有这种structure，则不能用动态规划，也就是说不能否决掉一些路径，那么只能暴力搜索了。
五、应用DP
- 建立状态转移方程
- 缓存并复用以往结果
- 按顺序从小往大算：这里的“小”和“大”对应的是问题的规模，在这里也就是我们要从f(0)、f(1)、···到f(n)依次计算。
参考：https://www.zhihu.com/question/39948290；
https://zhuanlan.zhihu.com/p/27033169；
网友评论