dp按照规模分类总结

本文章的内容来源于花花酱dp2。

做多了dp的题目之后总觉得有什么规律&＃xff0c;但是自己没总结出来。花花酱按照输入规模、子问题个数、在解决一个问题的时候需要依赖的子问题个数为特征对题目做了分类。

其中绿色是比较简单的 &＃xff0c;黄色是中等的&＃xff0c;粉色是比较难的。
对上面几种分类取其中一些做进一步分析&＃xff0c;写出模板。

1.1

输入O(n)
有n个子问题需要解决
每个子问题依赖常数个更小的子问题
时间复杂度&＃xff1a;O(n)
空间复杂度&＃xff1a;O(n)->O(1)
模板

dp &＃61; [0] * n;
for i &＃61; 1 to n:dp[i] &＃61; f(dp[i-1],dp[i-2]...)return dp[n]


LC 70:climbing stairs

dp[i] :&＃61; 到达第i级台阶的方法
dp[i] &＃61; dp[i-2] &＃43; dpp[i-1]


LC 198: house robber

dp[i][0] :&＃61; 从0到i&＃xff0c;抢第i个房间&＃xff0c;抢到的最大价值。
dp[i][1] :&＃61; 从0到i&＃xff0c;不抢第i个房间&＃xff0c;抢到的最大价值。
dp[i][0] &＃61; max(dp[i-2][1],dp[i-2][0])&＃43;A[i]
dp[i][1] &＃61; max(dp[i-1][0],dp[i-1][1])


LC 801 Minimum Swaps To Make Sequences Increasing

dp[i][0] :&＃61; 从0到i&＃xff0c;交换A[i]/B[i]的最小交换次数
dp[i][1] :&＃61; 从0到i&＃xff0c;不交换A[i]/B[i]的最小交换次数


1.2

输入O(n)
有n个子问题需要解决
每个子问题依赖所有比它小的子问题
时间复杂度&＃xff1a;O(n2n^2n2)
空间复杂度&＃xff1a;O(n)
模板

dp &＃61; new int[n]
for i &＃61; 1 to n:for j &＃61; 1 to i-1:dp[i] &＃61; max/min(dp[i],f(dp[j]))
return dp[n]


LC 139 word break

dp[i] :&＃61; wordbreak(A[0->i])
dp[i] &＃61; any(dp[k] && word(A[k&＃43;1->i]))


LC 818 race car

dp[i][0] :&＃61;到达位置i并且速度方向向右
dp[i][1] :&＃61;到达位置i并且速度方向向左
for k in range(1,i):c &＃61; min(dp[k][0]&＃43;2,dp[k][1]&＃43;1)dp[i][0] &＃61; min(dp[i][0],dp[i-k][0]&＃43;c)dp[i][1] &＃61; min(dp[i][1],dp[i-k][1]&＃43;c)


1.3

输入&＃xff1a;O(m)&＃43;O(n)
dp[i][j] :&＃61; 解决子问题(A[0->i],B[0->j])的答案
dp[i][j] 依赖常数个子问题的解
时间复杂度O(mn)
空间复杂度O(mn)
模板

dp &＃61; new int[m][n]
for i &＃61; 1 to m :for j &＃61; 1 to n:dp[i][j] &＃61; f(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])return dp[m][n]


LC 72 edit distance

dp[i][j] :&＃61; 从字符串A[0->i]变为B[0->j]最少操作数
dp[i][j] &＃61; f(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])


1.4?

输入&＃xff1a;O(n)
dp[i][j] :&＃61;子问题(A[i->j])的解&＃xff0c;A[i->j]是输入的子串或者子数组
每个子问题依赖O(n)更小的子问题
模板

dp &＃61; new int[n][m]
for l &＃61; 1 to n:for i &＃61; 1 to l:j &＃61; i&＃43;l-1for k &＃61; i to j:dp[i][j] &＃61; max(dp[i][j],f(dp[i][k],dp[k][j]))return dp[1][n]


LC 312 burst balloons

LC 664 strange printer

2.1

输入O(mn)
dp[i][j] :&＃61; 解决子问题(A[0->i][0-j])的解
每个子问题依赖常数个子问题
时间 复杂度O(mn)
空间复杂度O(mn)
模板&＃xff1a;

dp &＃61; new int[m][n]
for i &＃61; 1 to m:for j &＃61;1 to n:dp[i][j] &＃61; f(dp[i-1][j],dp[i][j-1])return dp[m][n] / max(dp[m])


LC 62 unique paths

dp[i][j] :&＃61; 从A[]0[0]到A[i][j]有几种方式
dp[i][j] &＃61; dp[i-1][j] &＃43; dp[i][j-1]


2.2

输入O(mn)
dp[k][i][j] :&＃61; 在k步之后解决子问题A[0->i][0-j])的解
每个子问题依赖一个子问题
时间复杂度O(kmn)
空间复杂度O(kmn)->O(mn)
模板

dp &＃61; new int[k][m][n]
for k &＃61; 1 to K:for i &＃61; 1 to m:for j &＃61; 1 to n:dp[k][i][j] &＃61; f(dp[k-1][i&＃43;di][j&＃43;dy])return dp[K][m][n]/m(dp[K])


LC 576