学习笔记

动态规划和递归没有根本上的区别，关键在于看问题是否有最优子结构。因为问题存在最优子结构的时候，可以在求解的中途直接淘汰掉次优解，仅保留最优解。因此动态规划的时间复杂度往往会低于普通递归。

动态规划求解步骤：

1. 寻找重复子问题
2. 定义状态数组
3. 写出状态转移方程

状态数组的含义不同，则最终的状态转移方程也会不同。