什么题可以用DP？
1. 最大值/最小值
2. 方案数
3. 可行性
怎么写DP
状态：DP数组的含义
* dp里面存什么？
题目要求什么，dp数组就存什么
* i的寄巧：
1. 使用了前i个元素的最佳答案(背包问题)
2. 使用了前i个元素且最后一个使用的元素是第i个元素的最佳答案(最长上升子序列)
* 想不出转移方程时的寄巧：
加一维
初始条件
如果状态无法通过转移方程得到，需要初始化
转移方程
最后一步 : 如何到达当前dp状态
循环顺序
在计算dp值的时候，需要已经算出所有前置dp值。
答案
题目所求的内容与dp数组的关系
DP模型
背包DP
01背包
dpi,j:dp_{i, j} :dpi,j : 考虑前 iii 个物品，且使用了 jjj 的空间收益最大值
dpi,j=max(dpi−1,j,dpi−1,j−wi+vi)dp_{i, j} = \max(dp_{i - 1, j}, dp_{i - 1, j - w_i} + v_i)dpi,j =max(dpi−1,j ,dpi−1,j−wi +vi )
完全背包
dpi,j:dp_{i, j} :dpi,j : 考虑前 iii 个物品，且使用了 jjj 的空间收益最大值
dpi,j=max(dpi−1,j,dpi,j−wi+vi)dp_{i, j} = \max(dp_{i - 1, j}, dp_{i, j - w_i} + v_i)dpi,j =max(dpi−1,j ,dpi,j−wi +vi )
时间复杂度
O(nm)O(nm)O(nm)
区间DP
> 将[l,r][l, r][l,r] 完全删除、XXX的方案数、合并成一个区间.
状态
$dp_{i, j} : $ 将区间 [i,j][i, j][i,j] 做XXX操作后可以获得的最大值/方案数。
$i: $ 区间左端点， $j: $ 区间右端点
转移方程
dpi,j=dpi,k+dpk+1,j(k∈[i,j−1])dp_{i, j} = dp_{i, k} + dp_{k + 1, j} (k \in [i, j - 1])dpi,j =dpi,k +dpk+1,j (k∈[i,j−1])
循环顺序
1. 先枚举区间长度，通过小区间获得大区间的答案
2. 枚举区间左端点
3. 枚举k （如果需要）
答案
dp1,ndp_{1, n}dp1,n
时间复杂度
O(n3)O(n^3)O(n3)
状压DP
状态
dpidp_idpi : i(010011)2i (010011)_2i(010011)2 表示选择了第0个、第1个、第4个物品的状态
转移方程
dp0100112←dp0100102dp_{010011_2} \leftarrow dp_{010010_2}dp0100112 ←dp0100102
答案
dp1111112dp_{111111_2}dp1111112
时间、空间复杂度
O(2n)O(2^n)O(2n)
线性DP
观察数据范围
O(n)或O(nlogn):dpi,j←dpi−1,jO(n) 或 O(n\log n): dp_{i, j} \leftarrow dp_{i - 1, j}O(n)或O(nlogn):dpi,j ←dpi−1,j
O(n2):dpi←dpj(j∈[1,i−1])O(n^2): dp_i \leftarrow dp_j (j \in [1, i - 1])O(n2):dpi ←dpj (j∈[1,i−1])
双序列DP
状态
dpi,jdp_{i, j}dpi,j 表示考虑第一个序列的前 iii 个元素和第二个序列的前 jjj 个元素时的最大值/最小值/方案数
转移方程
如果在原基础上增加一个字符会发生什么。如果增加第 iii 个字符,....
时间复杂度
O(n2)O(n^2)O(n2)
