学习笔记

• 动态规划和递归、分治 没有根本上的区别

• 共性：都是找重复子问题

• 差异性：动态规划有最优子结构，中途可以淘汰次优解，也必须淘汰次优解，加快执行速度

1. 提出总问题，然后提出子问题
2. 设计 DP 数组
3. 找到DP 方程

1. 最有子结构：opt[n] = best_of(opt[n-1],opt[n-2]...)
2. 存储中间状态: opt[i]
3. 递推公式(DP 方程):如：
   1. Fib:opt[i] = opt[i - 1] + opt[i - 2]
   2. 二维路径：opt[i,j] = opt[i + 1] [j] + opt[i] [j + 1]