前言
動態規劃是一種高效解決??重疊子問題??和??最優子結構??問題的算法思想。它通過??分治+記憶化??，將復雜問題分解為子問題，并存儲中間結果，避免重復計算，從而大幅提升效率。
??為什么重要？?
- ??優化暴力解法??：如斐波那契數列，遞歸復雜度為O(2n)，而動態規劃可優化至O(n)。
- ??解決經典難題??：如背包問題、最短路徑、編輯距離等，動態規劃往往是??最優解法??。
- ??廣泛應用??：從算法競賽到實際開發（如資源調度、股票交易策略），動態規劃都是核心工具之一。
掌握動態規劃，能讓你在算法設計與優化中事半功倍！
動態規劃流程
我個人是覺得動態規劃是相當難的，因為我不太擅長找規律
動態規劃就像是我們熟知的找規律，通過已知項得出一個規律
再用這個規律，套用到已知項上，得出未知項
雖然難，但動態規劃也有自己的模板，讓你看到一個動態規劃有個思考方向
動態規劃流程
- 創建dp表，確定狀態表示
- 確定狀態轉移方程
- 初始化
- 順序填充
- 確定返回值
現在，分別介紹一下
創建dp表，并確定狀態表示
??DP表（動態規劃表）??是動態規劃算法的核心工具。
它本質是一個數組，其中的每一個元素都是一個解
但這個解的意義是未知的，需要我們自己去規定，即解的狀態表示
直接地
例如:Fn = Fn-1 + Fn-2
- 我們創建一個dp表，此時dp[i]表示的值就是Fi的值
間接地
例如:求字符串中一個連續的無重復元素子串的最大長度
- 我們創建一個dp表，此時dp[i]表示的值就是以i位置為結尾的無重復元素子串的最大長度
確定狀態轉移方程
如何從已知的dp[i]得到未知的dp[i],就需要得出狀態轉移方程
這就是找規律，也是動態規劃最難的一部分，得出正確的狀態轉移方程，是解決問題的關鍵部分
有些狀態轉移方程是明著告訴你的，有些則需要自己去找
這一步相當考驗你的經驗，解決這一步的唯一方法:多練多思考多畫圖
順序填充
dp表的數據元素代表解，我們求解問題，就是求出指定dp[i]
用狀態轉移方程求出dp[i]，可能需要dp[i-1]、dp[i-2]等一個或者多個
有了前面，才有后面，因此必須順序填充
例如:Fn=Fn-1+Fn-2
- 我們求一個dp[i],就需要先知道dp[i-1]和dp[i-2]的長度
初始化
進行順序填充前，需要先做好準備工作，防止順序填充的時候遇到錯誤
例如:Fn = Fn-1+Fn-2
當你填充dp[1]的時候，你就會發現根本沒有所謂的F1-2和F1-1,這就是越界錯誤
我們需要用初始化來避免越界錯誤
確定返回值
具體情況具體分析，根據題目要求確定返回值，
例如:得出第幾項的值
- 這時候直接返回dp[i]即可
再者:求字符串中一個連續的無重復元素子串的最大長度
- 這時候就需要返回最大的dp[i]
動態規劃題型
斐波那契數列模型
斐波那契數列就是求出第幾個斐波那契數的值
這是最簡單的一類動態規劃題型，明明白白地告訴你怎么創建dp表，怎么進行狀態表示
屬于直接明牌了
流程解決:
- 創建dp表:創建一個大小為n+1的dp表，dp[i]表示的值即為F(i)
- 確定狀態轉移方程:F(n) = F(n-1) + F(n-2)
- 初始化:dp[0]=0,dp[1]=1
- 順序填充:從左往右依次填充
- 確定返回值:dp[n]表示的值就是F(n)的值，返回dp[n]即可
代碼如下
class Solution {
public:int fib(int n) {if(n==0) return 0;if(n==1) return 1;//創建dp表vector<int> dp(n+1);//初始化dp[0]=0;dp[1]=1;//順序填充for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}//返回結果return dp[n];}
};路徑問題
求出到達目標地點有多少種方式
這種就是需要自己來找規律了
經典例題:不同路徑
?
流程解決:
創建dp表，確定狀態表示
- 有多少個格子，dp表就需要多大，即dp表的大小就是m*n
- 狀態表示有個技巧，題目最后要什么，你就表示什么，要求返回抵達最后一個位置的所有路徑總數，則dp[i][j]代表的就是這個抵達這個位置的所有路徑總數
確定狀態轉移方程
這里的狀態轉移方程就沒有明示了，需要我們自己去找
但也不難到達一個格子只有兩種方式，從正上方的格子下來，從左方的格子過來
而到達當前格子的正上方格子有多種方式，到達左方格子也有多種方式
因此，到達當前格子總路徑數 = 到達上方格子的路徑數 + 到達右方格子的路徑數
狀態轉移方程:dp[i][j] = dp[i][j-1] + dp[i-1][j]
初始化
- dp[0][0]等于1
順序填充
- 從左往右，從上往下進行填充
- 填充的時候，需要注意左方格子和上方格子是否存在，進行取舍
確定返回值
- 返回最后一個格子對應的dp[i][j]即可
代碼:
class Solution {
public:int uniquePaths(int m, int n) {//創建dp表vector<vector<int>> dp(m,vector<int>(n,0));//初始化dp[0][0]=1;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(i==0 && j!=0){dp[i][j]+=dp[i][j-1];}if(j==0 && i!=0){dp[i][j]+=dp[i-1][j];}else if(i!=0 && j!=0){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}}return dp[m-1][n-1];}
};簡單多狀態
在常規動態規劃問題中，每個子問題通常只需一個狀態表示（如dp[i]）。但在??多狀態DP??中，每個步驟需要維護??多個并行的狀態??，通過它們之間的關系推導最終解。
??典型特征??：
- 問題在每個步驟有??多種可能的狀態??（如"持有/未持有股票"、"偷/不偷當前房屋"）
- 需要為??每種狀態單獨建立DP表??或狀態變量
- 狀態之間存在??相互轉移關系?
這是我個人問題有點難度的題型，因為你需要考慮多種狀態下的狀態表示
經典例題:打家劫舍
流程解決:
創建dp表
- 創建dp表,dp表的大小即為給定房屋的個數，即為n
- 狀態表示:dp[i]表示偷到當前房屋時的最大金額數
但此時房屋可能被偷，也可能沒有被偷!
- 被偷時，該房屋的最大金額數應該加上當前房屋的金額
- 沒有被偷時，該房屋的最大金額數則不應該加上當前房屋的金額
而一張dp表，是無法表示偷、不偷兩種狀態下的值的
因此，需要兩種dp表
- dpf表，dpf[i]表示當前房屋被偷后，所獲得的最大金額
- dpg表，dpg[i]表示當前房屋沒有被偷時，所獲得的最大金額
確定狀態轉移方程
當前房屋被偷
- 相鄰的房屋一定沒有被偷
dpf狀態轉移方程:dpf[i] = dpg[i] +nums[i];
當前房屋沒有被偷，相鄰的房屋可能被偷，也可能沒有被偷
- 上一個房屋沒有被偷時,狀態轉移方程:dpg[i] = dpg[i-1];
- 上一個房屋被偷時,狀態轉移方程:dpg[i] = dpf[i-1]
dpg[i]表示當前房屋沒有被偷時的最大金額，因此取兩者最大即可
dpg狀態轉移方程:dpg[i] = max(dpg[i-1],dpf[i-1])
初始化
從開始位置開始
- 偷,dpf[0] = nums[0]
- 沒偷,dpg[0] = 0;
順序填充
- 從左到右,依次填充兩個dp表
確定返回值
- 返回最后一個房屋的最大金額即可，即max(dpf[n-1],dpg[n-1])
代碼:
class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==0) return 0;//創建dp表int n = nums.size();vector<int> f(n);auto g = f;//初始化f[0]=nums[0];g[0]=0;//順序填充for(int i = 1;i<n;i++){f[i]=g[i-1]+nums[i];g[i]=max(g[i-1],f[i-1]);}return max(f[n-1],g[n-1]);}
};子數組問題
子數組問題是動態規劃的經典應用場景，通常涉及??連續子數組??的最優解（如最大和、最長長度等）
??子數組問題的DP特點
- ??連續性??：子數組要求元素連續，與子序列（可不連續）不同
- ??單串DP??：通常用
dp[i]表示??以第i個元素結尾的子數組的解?? - ??狀態轉移??：要么延續前一個狀態，要么從當前元素重新開始
經典例題:最大子數組和
流程解決:
創建dp表，確定狀態表示
- 創建一個大小和數組大小一樣的dp表
- 狀態表示:dp[i]表示以i位置為結尾的子數組的最大和
確定狀態轉移方程
連續的子數組，所有下標必須連續，不能間斷
- dp[i] = dp[i-1] + nums[i]
子數組可以是多個，也可以是一個，即從當前下標開始
- dp[i] = nums[i]
dp[i]記錄的是以i位置為結尾的子數組的最大和,取兩者中的最大值
狀態轉移方程:dp[i] = max(dp[i-1]+nums[i],nums[i])
初始化
- dp[0] = nums[0]
順序填充
- 從左向右，依次對dp表進行填充
確定返回值
- 我們需要的是該數組的最大子數組和，并不是最后一個位置的最大子數組和
- 所以我們需要找到dp表中的最大值，并返回
代碼:
class Solution {
public:int maxSubArray(vector<int>& nums) {if(nums.size()==0) return 0;if(nums.size()==1) return nums[0];//創建dp表:dp[i]表示當前位置的最大連續子數組和int n = nums.size();vector<int> dp(n);//初始化dp[0]=nums[0];int ret = nums[0];//順序填充for(int i=1;i<n;i++){dp[i]=max(nums[i],dp[i-1]+nums[i]);if(dp[i]>ret) ret = dp[i];}return ret;}
};子序列問題
子序列問題是動態規劃中的另一大類經典問題，與子數組問題最大的區別在于??元素不需要連續??。
經典例題:最長遞增子序列
流程解決:
創建dp表,確定狀態表示
- 創建一個和數組大小一樣的dp表
- 狀態表示:dp[i]的值表示以i位置為結尾的遞增子序列的最大長度
確定狀態轉移方程
- 遞增子序列可以有多個元素，這是元素可以連續，也可以不連續
- dp[i] = dp[j] + 1;
注意:這里的dp[j]可能并不與dp[i]相鄰，可以相鄰，也可以不相鄰，前提是滿足nums[j]<nums[i]
- 遞增子序列也可能只有一個元素，即當前元素，代表之前沒有比其小的元素
- dp[i] = 1
而dp[i]表示的是以i位置為結尾的遞增子序列的最大長度
很多人可能會覺得需要在這兩者中取最大值
但并不是，這里只能選擇符合要求的值
一旦前面沒有比當前元素小的元素，那么遞增子序列只能重頭開始，即長度為1
而如果有，則就需要再在原來的基礎長度上加1即可
所以，我們可以在創建dp表的時候，就將所有的dp[i]設置為1
后續如果nums[i]的前面有更小值，直接更新即可！
初始化
- 不需要初始化
順序填充
- 從左往右依次填充dp表
確定返回值
- 返回dp表中的最大的dp[i]
回文串問題?
回文串問題是動態規劃的經典應用場景，通常涉及??子串/子序列的回文性質判斷??和??最值計算??。以下是系統性解題框架和典型例題分析。
??回文串問題的DP特點??
- ??對稱性??：需判斷字符串的對稱性質（如
s[i]==s[j]） - ??中心擴展??：多數問題可轉化為??區間DP??（從短子串向長子串遞推）
- ??狀態定義??：通常用
dp[i][j]表示??子串s[i..j]的回文性質?
經典例題:回文子串
思路:
將給定字符串的所有子串進行枚舉，并對其每個進行判斷是否是回文串
這里的枚舉并不是真正的枚舉，而是進行一種映射
如:使用[i,j],表示一段區間
流程解決:
創建dp表,確定狀態表示
- 根據給定的字符串大小n，創建一個n*n的dp表
- 狀態表示:dp[i,j]:表示s中區間為[i,j]的子串是回文字符串
例如:s="abcter"?
dp[0][2] 表示"abc"是否是回文字符串
確定狀態轉移方程
判斷 s 的區間[i,j]是否是回文子串
如果 s[i] == s[j] , 則分三種情況進行判斷?
- i == j,[i,j]代表一個字符，則dp[i][j]=true
- i+1 == j,[i,j]代表兩個相鄰的字符，則dp[i,j]=true
- i+1 <j,代表不相鄰的兩個字符相同，接下來看看dp[i+1][j-1]是否是回文字符串
所以，狀態轉移方程:dp[i][j] = i+1<j?dp[i+1][j-1]:true;
初始化
- 將dp表中的所有元素置為false
順序填充
- 這里的順序填充不在是我們正常思維的順序，而是倒序
- 在狀態轉移方程中，我們可以發現，求dp[i][j]可能需要dp[i+1][j-1]，而dp[i+1][j-1]在dp[i][j]的左下方
- 因此填充順序是從下到上，從左到右
確定返回值
- 首先設置一個計數器
- 遍歷一遍dp表，遇到true就讓計數器+1
- 最后返回計數器的值即可
結語
? 動態規劃是一種將復雜問題分解為相互關聯的子問題的算法思想，其核心在于利用最優子結構和避免重復計算來提升效率。我們通過定義狀態、建立轉移方程、初始化邊界條件和確定計算順序這四個關鍵步驟，可以系統性地解決各類動態規劃問題。無論是求最值、處理序列問題，還是解決背包或狀態機問題，動態規劃都展現出強大的建模能力。記住，許多看似復雜的問題，往往都能通過尋找子問題之間的遞推關系來優雅解決。動態規劃的魅力就在于它用空間換時間的智慧，讓原本可能指數級復雜度的問題變得可解。
