- 动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构）
- 共性： 找到重复子问题（for 、 else 、 loop）
- 差异性：最优子结构、中途可以淘汰次优解
- 最优子结构 opt[n] = best_of(opt[n - 1], opt[n - 2]...)
- 存储中间状态：opt[i]
- 递推公式 - 状态转移方程或 DP方程 Fib: opt[n] = opt[n - 1] + opt[n - 2] 二维路径： opt[i,j] = opt[i+1][j] + opt[i][j+1](且判断 a[i,j]是否空地)
- 分治 - 找重复性
- 定义状态空间
- 记忆化搜索递归或者从下到上进行 DP 的顺推（自底向上推导）