記錄寫過的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)