总论
怎么求解？
- 回溯
- 记忆化搜索
- 递推(方便进行空间复杂度优化)
求什么？
- 方案数
- 最大值
- 最小值
状态方程
对应关系：
- 转移状态的定义（回溯入口）
- 边界条件（边界状态如何递推得到其实状态，回溯的终止条件）
- 如果递推公式是求最小，边界初始化成INT_MAX_ * 如果递推公式求最大，边界为0或1
- 如果是乘法，需要处理负数正数两种状态
- 取一个特例: 从单个元素角度看一下
空间复杂度优化
- O(mn)->O(n) 滚动数组，注意方向
- O(mn)->O(1) 单个变量记录状态
分类
| 分类 | 递推公式 | 边界条件 | 备注 |
|---|---|---|---|
| 爬楼梯（方案数） | dp(i) = dp(i-1) + dp(i-2) |
起始位置f(0), f(1), f(2) | O(n), 加法原理+取余 |
| 打家劫舍（选与不选） | dp(i) = max(dp(i-1), + dp(i-2)+value[i-1]) |
起始位置 | O(n), 选与不选 |
| 最大子数组和（选与不选） | dp(i) = max(nums(i), dp(i-1)+nums(i-1)); |
无需处理 | Kadane算法，还有前缀和做法（滑动窗口找当前前缀和减当前最小前缀和） |
| 网格dp | dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1]; |
起始位置+最左和最上的边界 | O(n)(m),通常是2D网格，注意空间优化 |
| 0-1背包（选与不选） | dp[i] = max(dp[i-1][c], dp[i-1][c-w[i]]+v[i]) |
起始位置与默认值 | O(n)(value), 空间复杂度优化 |
| 完全背包（选与不选） | dp[i] = max(dp[i-1][c], dp[i][c-w[i]]+v[i]) |
起始位置与默认值 | O(n)(value), 空间复杂度优化 |
| 多重/分组背包（选几次） | dp[i] = \sum{dp[i-1][j-v*i]} for i=1..k |
起始位置dp(0)(0)=1默认值0 | O(n)(value)，同一物品可选k次，空间复杂度与其他背包一样,多重背包k在外面，分组k在里面 |
| 线性序列dp (LCS, LIS问题，2个字符串s1(:i), s2(:j)的关系) | dp[i][j] = max(dp[i-1][j], dp[i][j-1]); |
边界条件多1行1列，初始值受问题影响 | O(m)(n), 一般是在数组前缀和后缀上转移的，空间复杂度优化 |
| 状态机dp | f[i][j]为第i天在j状态下，需要与i-1天建立联系，如股票买卖 |
边界条件，可能为-∞ | O(n), 画状态图，适合dfs |
| 划分型dp | |||
| 区间dp | dp[i][j]=dp[i+1]dp[j-1]+2;``dp[i][j]=max(dp[i+1][j], dp[i][j-1]) |
边界条件主要是允许区间越界的地方如何表示（上三角矩阵），和循环变量增长的方向。 | O(m)(n), 从小区间转移到大区间 |
最长递增子序列LIS问题的优化
- 从O(n2)到O(n)，思路：交换状态与状态值
- O(n2): 状态是以i为结尾元素的LIS的长度
- O(n): 状态是长度为i+1的序列里面构成的上升子序列结尾元素最小值（最小值，才有机会扩展序列）贪心+二分
注意此时记录的额外空间g(n)不是子序列
带特殊数据结构的DP
- 前缀和优化
- 单调栈优化
- 单调队列优化
- 树状数组优化