-
动态规划区别于（递归和分治）的主要在于最优子结构，中途可以淘汰次优解。
-
动态规划关键点：
- 最优子结构 opt[n] = best_of(opt[n-1], opt[n-2], …)
- 储存中间状态：opt[i]
- 递推公式（美其名曰：状态转移方程或者 DP 方程）
- 能采用动态规划求解的问题的一般要具有3个性质：
- 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
- 无后效性 ：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
- 有重复子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
- 动态规划小结：
- 打破自己的思维惯性，形成机器思维
- 理解复杂逻辑的关键
- 也是职业进阶的要点要领
- 动态规划这一章节主要需要动手练习，能够分析整理DP方程。