本文章的內容來源于花花醬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($n^2$)
空間復雜度：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[k+1->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 = i+l-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][i+di][j+dy])return dp[K][m][n]/m(dp[K])

LC 576

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的dp按照规模分类总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。