西安网站快速优化,门户网站兴化建设局 金,适合html初学者做的网站,响应式网站 企业模版本文章的内容来源于花花酱dp2。
做多了dp的题目之后总觉得有什么规律#xff0c;但是自己没总结出来。花花酱按照输入规模、子问题个数、在解决一个问题的时候需要依赖的子问题个数为特征对题目做了分类。 其中绿色是比较简单的 #xff0c;黄色是中等的#xff0c;粉色是…本文章的内容来源于花花酱dp2。
做多了dp的题目之后总觉得有什么规律但是自己没总结出来。花花酱按照输入规模、子问题个数、在解决一个问题的时候需要依赖的子问题个数为特征对题目做了分类。 其中绿色是比较简单的 黄色是中等的粉色是比较难的。 对上面几种分类取其中一些做进一步分析写出模板。
1.1
输入O(n) 有n个子问题需要解决 每个子问题依赖常数个更小的子问题 时间复杂度O(n) 空间复杂度O(n)-O(1) 模板
dp [0] * n;
for i 1 to n:dp[i] f(dp[i-1],dp[i-2]...)return dp[n]LC 70:climbing stairs
dp[i] : 到达第i级台阶的方法
dp[i] dp[i-2] dpp[i-1]LC 198: house robber
dp[i][0] : 从0到i抢第i个房间抢到的最大价值。
dp[i][1] : 从0到i不抢第i个房间抢到的最大价值。
dp[i][0] max(dp[i-2][1],dp[i-2][0])A[i]
dp[i][1] max(dp[i-1][0],dp[i-1][1])LC 801 Minimum Swaps To Make Sequences Increasing
dp[i][0] : 从0到i交换A[i]/B[i]的最小交换次数
dp[i][1] : 从0到i不交换A[i]/B[i]的最小交换次数1.2
输入O(n) 有n个子问题需要解决 每个子问题依赖所有比它小的子问题 时间复杂度O(n2n^2n2) 空间复杂度O(n) 模板
dp new int[n]
for i 1 to n:for j 1 to i-1:dp[i] max/min(dp[i],f(dp[j]))
return dp[n]LC 139 word break
dp[i] : wordbreak(A[0-i])
dp[i] any(dp[k] word(A[k1-i]))LC 818 race car
dp[i][0] :到达位置i并且速度方向向右
dp[i][1] :到达位置i并且速度方向向左
for k in range(1,i):c min(dp[k][0]2,dp[k][1]1)dp[i][0] min(dp[i][0],dp[i-k][0]c)dp[i][1] min(dp[i][1],dp[i-k][1]c) 1.3
输入O(m)O(n) dp[i][j] : 解决子问题(A[0-i],B[0-j])的答案 dp[i][j] 依赖常数个子问题的解 时间复杂度O(mn) 空间复杂度O(mn) 模板
dp new int[m][n]
for i 1 to m :for j 1 to n:dp[i][j] 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] : 从字符串A[0-i]变为B[0-j]最少操作数
dp[i][j] f(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])1.4?
输入O(n) dp[i][j] :子问题(A[i-j])的解A[i-j]是输入的子串或者子数组 每个子问题依赖O(n)更小的子问题 模板
dp new int[n][m]
for l 1 to n:for i 1 to l:j il-1for k i to j:dp[i][j] 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] : 解决子问题(A[0-i][0-j])的解 每个子问题依赖常数个子问题 时间 复杂度O(mn) 空间复杂度O(mn) 模板
dp new int[m][n]
for i 1 to m:for j 1 to n:dp[i][j] f(dp[i-1][j],dp[i][j-1])return dp[m][n] / max(dp[m])LC 62 unique paths
dp[i][j] : 从A[]0[0]到A[i][j]有几种方式
dp[i][j] dp[i-1][j] dp[i][j-1]2.2
输入O(mn) dp[k][i][j] : 在k步之后解决子问题A[0-i][0-j])的解 每个子问题依赖一个子问题 时间复杂度O(kmn) 空间复杂度O(kmn)-O(mn) 模板
dp new int[k][m][n]
for k 1 to K:for i 1 to m:for j 1 to n:dp[k][i][j] f(dp[k-1][idi][jdy])return dp[K][m][n]/m(dp[K]) LC 576
