记录写过的dp题目，并分类，尝试总结出某类题目的一般模型.
(题目前打*的未编程验证)
【线性模型】
Tyvj 1049 最长不下降子序列问题 [O(n^2) [还存在基于二分查找的O(nlogn)算法]]
- [状态] f[i]表示从1到i的最长不下降子序列. 最大值需更新.
- [方程] if(a[j]<=a[i]) f[i] = max{f[j]} (0<j<i, 1<i<=n)
NOIp 2004 合唱队形 [O(n^2), 双向最长上升子序列]
- [方程] f[i] = max{f[j]}+1 , 枚举k(0<=k<=n).
Rqnoj 164 最长公共子串 [记录方案 子串连续 O(n^2)]
- [状态] f[i][j]表示 子串A第i个字符 和 子串B第j个字符 前 公共子序列长度
- [方程] f[i][j] = f[i-1][j-1]+1(a[i]=b[j],a[i-1]=b[j-1])|max{f[i-1][j],f[i][j-1]}
UVa 111/10405 [最长公共子序列问题,O(n^2). 可以使用滚动数组降至O(n).]
- [状态] f[i][j]表示 子串A第i个字符 和 子串B第j个字符 前 公共子序列长度
- [方程] f[i][j] = f[i-1][j-1]+1(a[i]=b[j])|max{f[i-1][j],f[i][j-1]}
UVa 507 [最大连续和,O(n).]
- [状态] f[i]表示当前子序列和(非负)
- [方程] f[i]=max{f[i-1]+a[i], a[i]},递推过程中需更新最大值.
【矩阵模型】
*UVa 10285 滑雪 [记忆化搜索,最长下降子序列二维版本]
- [状态] f[i][j]表示从(i,j)开始的最长下降子序列长度.
- [方程] f[i][j] = max{f[i-1][j], f[i][j-1], f[i+1][j], f[i][j+1]}+1(f[i][j]>f[i-1][j]..)
UVa 108
- 最大矩阵和，O(n^3)，方程不会. 最大连续和的二维版本.
NOIp 2000 方格取数 O(n^4)
- [状态] f[i][j][k][l]表示两人分别到(i,j)、(k,l)所取过的数的和.G[i][j]表示方格里的数.
- [方程] f[i][j][k][l] = max{f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1]}+G[i][j]+(i==k&&j==l ? 0 : G[k][l])
NOIp 2008 传纸条
(1) O(n^4)
- [状态] f[x1][y1][x2][y2] 表示从出发点分别到(x1,y1)、(x2,y2)取的最大值.G[x][y]表示该格的数.
- [方程] f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1]}+G[x1][y1]+G[x2][y2](如果位置不重复)
- [一个重要优化] 显然有y2=x1+y1-x2(y2>0),因而时间复杂度可以降到O(n^3).Cena显示总用时从近4s降到近0.3s，效果明显.
*(2) O(n^3)
- [状态] f[p][x1][x2],p表示经过的格子数.
- [方程] f[p][x1][x2]=max{f[p-1][x1-1][x2-1],f[p-1][x1-1][x2],f[p-1][x1][x2-1],f[p-1][x1][x2]}+G[x1][p-x1]+G[x2][p-x2](如果位置不重复)
USACO 5.3.4/3.3.4 [矩阵dp,O(n^2)]
- [状态] f[i][j]表示以(i,j)为右下角的正方形最大边长
- [方程] f[i][j] = min{f[i-1][j], f[i-1][j-1], f[i][j-1]}+1 (0<=i,j<n)
- [预处理] 若G[i][j]=1则f[i][j]=1.
【背包问题】
USACO 3.3.2
- [状态] f[a1][a2][a3][a4][a5]为买a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5时，所需的最少价格
- [方程] f[a1][a2][a3][a4][a5] = min{f[a1-p[i][1][a2-p[i][2][a3-p[i][3][a4-p[i][4]][a5-p[i][5]+p[i][0]} (0<i<=s, ak-p[i][k]>=0,p[i][0]是优惠后的价格)
- [边界条件] f[0][0][0][0][0]=0;
- USACO官方解法很有启发性，用最短路，把每种状态[a1][a2][a3][a4][a5]（a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5）看成一个点，则至多7776个点，而每个优惠就是一条边，则至多105条边。 接下来就是求[0,0,0,0,0]到目标状态的最短路，用Dijkstra(Heap优化)即可.
USACO 3.1.2 [完全背包问题, O(n)或O(n^2).]
- [状态] f[i][j]表示放入第i个物体后剩余体积为j
- [方程] f[i][j] = f[i-1][j] + f[i][j-c[i]]+w[i]
USACO 3.1.6 [完全背包问题,O(n).]
- [状态] f[i]表示凑成i分邮资的最少邮票数.
- [方程] f[i] = min{f[i-v[j]]+1} (i-v[j] >= 0, 0<=i<n, f[0] = 0).
USACO 2.3.4
- [状态] f[i,j]表示前i种货币构成j的方法数，用c[i]记录货币的面值.
- [方程] f[i,j]=f[i-1,j]; 不用第i种货币
f[i,j]=f[i-1,j]+f[i,j-c[i]] 用第i种货币，j>=c[i]
【树形】
USACO 2.3.2
- [状态] f[i,j]表示用i个点组成深度最多为j的二叉树的方法数，则：
- [方程] f[i,j]=∑(f[k,j-1]×f[i-1-k,j-1])(k∈{1..i-2})
- [边界] f[1,i]=1
- 我们要求的是深度恰好为K的方法数S，易知S=f[n,k]-f[n,k-1]。但需要注意的是，如果每次都取模，最后可能会有f[n,k]<f[n,k-1],所以可以用S=(f[n,k]-f[n,k-1]+v) mod v
【其他类型】
USACO 1.5.1 [数字三角形]
- [状态] f[i][j]表示从(i,j)开始经过的数字的最大和
- [方程] f[i][j] = max{f[i+1][j], f[i+1][j+1]}+a[i][j]
USACO 3.3.5 [博弈问题]
- [状态] s[i][j]表示从i加到j的和, 枚举l=j-i. f[i][j]表示从i到j先取者能得到的最大数字和.
- [方程] f[i][j] = s[i][j] - min{f[i+1][j], f[i][j-1]}
USACO 3.2.2
- [状态] f[n][m]表示至多m个1的n位二进制数数量
- [方程] f[n][m] = f[n-1][m] + f[n-1][m-1] (f[0][m] = 1)