Dynamic Programming： intermediate result are “cached" for future calls
什么情况下可能动态规划
- 最大值最小值/是否可行/方案总数
什么情况不用动态规划
求所有方案/集合而不是序列求所有方案基本都是用recursion/DFS- 输入数据是集合而不是序列
- 暴力算法复杂度已经是多项式级别
- DP擅长优化指数级别复杂度(2^n, n!)到多项式级别复杂度(n^2, n^3)
- 不擅长优化n^3到n^2
解决动态规划问题的四点要素:
- 状态: 存储小规模问题的结果
- 方程: 状态之间的联系，怎么通过小的状态，来算大的状态
- 初始化: 最极限的小状态是什么, 起点
- 答案: 最大的那个状态是什么，终点
三种面试常见的动态规划类别及状态特点
坐标，单序列，双序列
一些奇技淫巧
- 初始化第0行和第0列（不能通过递归方程得到的状态需要初始化）
- n个数开n+1个位置的数组
- 二维网格类题目小技巧：
正方形用右下角作为定位角(A[i][j]+边长)
长方形用左上角和右下角做定位角
空间优化:滚动数组
一维：需要存储的状态为2个的情况下
f[i] = max(f[i-1], f[i-2]+A[i])装化为 f[i%2] = max(f[(i-1)%2], f[(i-2)%2])
二维：f[i][j]由f[i-1]行决定于之前行无关，即f[i%2][j]由f[(i-1)%2]行来决定
动归实现方式：
a) 循环：从小到大递推
b) 记忆化搜索：从大到小（画搜索树帮助确定状态，并剪支）
什么时候用记忆化搜索：
- 状态转移麻烦，不是顺序
- 初始化状态难以找到
博弈类DP： 有先手后手
state: 定义一个人的状态，通常是先手
function: 考虑两人的状态做更新
initializ: 根据最初几步操作进行初始化
answer:
区间类DP（一般都是O(n^2)）
- 求一段区间[0, n-1]的解min/max/count
- 转移方程通过区间更新
- 从大到小更新（逆向思维）
背包类DP
- 用值作为DP维度
- DP过程就是填写矩阵
- 可以滚动数组优化