什么是動態規劃算法
動態規劃(Dynamic Programming,簡稱 DP)是一種通過分解復雜問題為重疊子問題,并存儲子問題的解以避免重復計算,從而高效求解具有特定性質(重疊子問題、最優子結構)問題的算法思想。
一、核心思想:“分解 + 復用”
動態規劃的核心在于:
1.將原問題拆解為規模更小的子問題;
2.求解子問題后,將結果存儲起來(記憶化),避免后續重復計算;
3.基于子問題的解,推導出原問題的解。
簡單來說,就是 “用已知的子問題答案,解決未知的大問題”,本質是用空間換時間。
二、動態規劃的 2 個關鍵前提
只有當問題滿足以下兩個條件時,才能用動態規劃求解:
- 重疊子問題
問題可以分解為多個重復出現的子問題。
例如:計算斐波那契數列 f(n) = f(n-1) + f(n-2) 時,f(5) 依賴 f(4) 和 f(3),f(4) 又依賴 f(3) 和 f(2)——f(3) 就是被重復計算的重疊子問題。- 最優子結構(Optimal Substructure)
問題的最優解包含子問題的最優解。
例如:求 “從 A 到 B 的最短路徑” 時,若路徑 A→C→B 是最優解,則 A→C 和 C→B 一定分別是 A 到 C、C 到 B 的最短路徑(子問題的最優解)。
三、動態規劃的 2 種實現方式
動態規劃通常有兩種實現思路,核心都是 “存儲子問題的解”,只是順序不同:
- 自頂向下(Top-Down):遞歸 + 記憶化
思路:從原問題出發,遞歸分解為子問題,用備忘錄(數組或哈希表) 存儲已求解的子問題答案,避免重復計算。- 自底向上(Bottom-Up):迭代 + DP 表
思路:從最小的子問題開始,按順序求解,用DP 表(數組) 記錄子問題的解,逐步推導出原問題的解。
四、經典應用場景
動態規劃廣泛用于求解 “最優問題” 或 “計數問題”,典型案例包括:
計數問題:爬樓梯(方法數)、不同路徑(網格中路徑數);
最優問題:最長公共子序列(LCS)、最大子數組和、0-1 背包問題(最大價值);
其他:編輯距離(字符串相似度)、打家劫舍(不相鄰房屋最大金額)等。
五、動態規劃與其他算法的區別
與遞歸:遞歸可能重復計算子問題,動態規劃通過記憶化避免重復,效率更高;
與貪心算法:貪心只做局部最優選擇,不依賴子問題的解;動態規劃則基于子問題的最優解推導全局最優;
與分治法:分治法(如歸并排序)的子問題不重疊,無需存儲解;動態規劃的子問題重疊,必須存儲解。
一. (62.)不同路徑(力扣)
1.1算法原理
- 狀態表?:
對于這種「路徑類」的問題,我們的狀態表??般有兩種形式:
i. 從 [i, j] 位置出發,巴拉巴拉;
ii. 從起始位置出發,到達 [i, j] 位置,巴拉巴拉。
這?選擇第?種定義狀態表?的?式:
dp[i][j] 表?:?到 [i, j] 位置處,?共有多少種?式。
- 狀態轉移?程:
從最近的一步將問題劃分為子問題,再由若干個子問題來來解決總問題。dp[i][j] 表?到達 [i, j] 位置的?法數,到達 [i, j] 位置之前的??步,有兩種情況:
i. 從 [i, j] 位置的上?( [i - 1, j] 的位置)向下??步,轉移到 [i, j] 位置;
ii. 從 [i, j] 位置的左?( [i, j - 1] 的位置)向右??步,轉移到 [i, j] 位置。
由于我們要求的是有多少種?法,因此狀態轉移?程就呼之欲出了: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 。為什么方法數不將這一小步也加上?
因為這一小步不是方法數,而是一種方法中延申的一步,是路長步數,不影響方法數
3.初始化
通過添加虛擬節點來避免復雜邊界問題討論,需注意:
1.虛擬節點的值要保證后續填表是正確的
2.下標映射關系
在左上角第一個位置的上邊或左邊初始化為1,其他地方初始化為0,就不會影響后續填表
- 填表順序:
根據狀態轉移?程的推導來看,填表的順序就是從上往下填每??,在填寫每??的時候從左往右。
- 返回值:
根據狀態表?,由于多增加了一行一列的虛擬節點,我們要返回 dp[m][n] 的值(原本返回坐標為m-1,n-1)。
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1));//初始化dp表的虛擬節點一行一列,將[0][1]或[1][0]位置賦1即可其他默認為0dp[1][0]=1;//填表for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}
};
二. (63.) 不同路徑 II(力扣)
2.1算法原理
- 狀態表示:
dp[i][j] 表?:?到 [i, j] 位置處,?共有多少種?式。
- 狀態轉移:
到達 [i, j] 位置之前的??步,有兩種情況:
i. 從 [i, j] 位置的上?( [i - 1, j] 的位置)向下??步,轉移到 [i, j] 位置;
ii. 從 [i, j] 位置的左?( [i, j - 1] 的位置)向右??步,轉移到 [i, j] 位置。
但是, [i - 1, j] 與 [i, j - 1] 位置都是可能有障礙的,此時從上?或者左邊是不可能到達 [i, j] 位置的,也就是說,此時的?法數應該是 0。若dp[i][j]位置本身就有障礙物方法數直接為0
由此我們可以得出?個結論,只要這個位置上有障礙物,那么我們就不需要計算這個位置上的值,直接讓它等于 0 即可。
3.初始化
通過添加虛擬節點來避免復雜邊界問題討論,需注意:
1.虛擬節點的值要保證后續填表是正確的
2.下標映射關系
在左上角第一個位置的上邊或左邊初始化為1,其他地方初始化為0,就不會影響后續填表
- 填表順序:
根據狀態轉移?程的推導來看,填表的順序就是從上往下填每??,在填寫每??的時候從左往右。
- 返回值:
根據狀態表?,由于多增加了一行一列的虛擬節點,我們要返回 dp[m][n] 的值(原本返回坐標為m-1,n-1)。
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int n=obstacleGrid.size(),m=obstacleGrid[0].size();vector<vector<int>> dp(n+1,vector<int>(m+1));//初始化dp[0][1]=1;//填表for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(obstacleGrid[i-1][j-1]!=1)dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[n][m];}
};
三. 劍指 Offer 47. 禮物的最大價值(力扣)
3.1算法原理
1.狀態表示:
dp[i][j] 表?:?到 [i, j] 位置處,此時的最?價值。
- 狀態轉移?程:
對于 dp[i][j] ,想要到達 [i, j] 位置,有兩種?式:
i. 從 [i, j] 位置的上? [i - 1, j] 位置,向下??步,此時到達 [i, j] 位置能
拿到的禮物價值為 dp[i - 1][j] + grid[i][j] ;
ii. 從 [i, j] 位置的左邊 [i, j - 1] 位置,向右??步,此時到達 [i, j] 位置能
拿到的禮物價值為 dp[i][j - 1] + grid[i][j]
我們要的是最?值,因此狀態轉移?程為:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
3.初始化
1.依舊是添加一行一列的虛擬節點,需注意的是與前兩道題不同的是前兩題求的是路徑,本題求的是每個節點的“價值”,所以不能讓虛擬節點影響到原本節點的價值,由狀態轉移方程可知,求一個節點的最大價值,總共有兩種路徑取大的一方,題目要求所有值都>=0,所以將所有虛擬節點初始化為0就沒有影響
2.保證后續填表正確,注意dp表與原數組下標的映射關系
- 填表順序:
從上往下填寫每??,每??從左往右。
5.返回值
由于多添加了一行一列的虛擬節點,返回 dp[m][n] 的值
class Solution {
public:int jewelleryValue(vector<vector<int>>& f) {int m=f.size(),n=f[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1));//填表,初始化虛擬節點為0自動完成for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1])+f[i-1][j-1];}}return dp[m][n];}
};
四. (931.) 下降路徑最小和(力扣)
4.1算法原理
- 狀態表?
dp[i][j] 表?:到達 [i, j] 位置時,所有下降路徑中的最?和。
- 狀態轉移?程:
對于普遍位置 [i, j] ,根據題意得,到達 [i, j] 位置可能有三種情況:
i. 從正上? [i - 1, j] 位置轉移到 [i, j] 位置;
ii. 從左上? [i - 1, j - 1] 位置轉移到 [i, j] 位置;
iii. 從右上? [i - 1, j + 1] 位置轉移到 [i, j] 位置;
我們要的是三種情況下的「最?值」,然后再加上矩陣在 [i, j] 位置的值。
于是 dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i][j]
3.初始化
與前幾道題增加一行一列的初始化不同,本題要增加兩列一行,因為當前位置值受上一行左中右三個值的影響,所以原數組中最右邊一列的值也面臨初始化的問題,所以也需要增加虛擬節點
1.因為所求為下降路徑的最小和,所以除第一行外的其他虛擬節點需要初始化為正無窮大,同時原數組第一行沒有之前的下降路徑,所以不能受虛擬節點的影響,第一行虛擬節點要設為0。
2.可以采取先將全部虛擬節點初始化為正無窮大然后將第一行改為0
- 填表順序:
從上往下
- 返回值:
注意這?不是返回 dp[m][n] 的值!
題?要求只要到達最后??就?了,因此這?應該返回 dp 表中最后??的最?值
class Solution {
public:int minFallingPathSum(vector<vector<int>>& m) {int x=m.size(),y=m[0].size();vector<vector<int>> dp(x+1,vector<int>(y+2,INT_MAX));//初始化for(int j=0;j<=y+1;j++){dp[0][j]=0;}//填表for(int i=1;i<=x;i++){for(int j=1;j<=y;j++){dp[i][j]=min({dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]})+m[i-1][j-1];}}//找到最小返回值int ret=INT_MAX;for(int i=x,j=1;j<=y;j++){if(dp[i][j]<ret) ret=dp[i][j];}return ret;}
};
五. (64.) 最小路徑和(力扣)
5.1算法原理
- 狀態表?:
dp[i][j] 表?:到達 [i, j] 位置處,最?路徑和是多少。
- 狀態轉移:
表?到達 到達 [i, j] 位置處的最?路徑和,那么到達[i, j] 位置之前的??步,有兩種情況:
i. 從 [i - 1, j] 向下??步,轉移到 [i, j] 位置;
ii. 從 [i, j - 1] 向右??步,轉移到 [i, j] 位置。
由于到 [i, j] 位置兩種情況,并且我們要找的是最?路徑,因此只需要這兩種情況下的最?值,再加上 [i, j] 位置上本?的值即可。
也就是: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
- 初始化:
添加??,并且添加?列后,所有位置的值可以初始化為?窮?,然后讓
dp[0][1] = dp[1][0] = 1 即可。(因為求的是最小值,不能讓虛擬節點干擾)
- 填表順序:從上往下填每??,每??從左往后
- 由于多加了一行一列的虛擬節點,返回dp[m][n]
class Solution {
public:int minPathSum(vector<vector<int>>& g) {int m=g.size(),n=g[0].size();//創建dp表順便初始化vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));//特殊初始化值dp[1][0]=dp[0][1]=0;//填表for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=min(dp[i-1][j],dp[i][j-1])+g[i-1][j-1];}}return dp[m][n];}
};
六. (174.) 地下城游戲(力扣)
6.1算法原理
- 狀態表?:
這道題如果我們定義成:從起點開始,到達 [i, j] 位置的時候,所需的最低初始健康點數。那么我們分析狀態轉移的時候會有?個問題:那就是我們當前的健康點數還會受到后?的路徑的影響。也就是從上往下的狀態轉移不能很好地解決問題。
這個時候我們要換?種狀態表?:從 [i, j] 位置出發,到達終點時所需要的最低初始健康點數。這樣我們在分析狀態轉移的時候,后續的最佳狀態就已經知曉。
綜上所述,定義狀態表?為:
dp[i][j] 表?:從 [i, j] 位置出發,到達終點時所需的最低初始健康點數
- 狀態轉移?程:
在 [i, j] 位置的最低健康點數加上這?個位置的消耗,應該要?于等于右邊或下邊位置的最低健康點數。(圖中d代表dungeon)
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
注意:
如果當前位置dungeon[i][j] 是?個?較?的正數的話, dp[i][j] 的值可能變
成 0 或者負數。也就是最低點數會?于 1 ,那么騎?就會死亡。因此我們求出來的 dp[i][j] 如果?于等于 0 的話,說明此時的最低初始值應該為 1 。處理這種情況僅需讓 dp[i][j] 與 1 取?個最?值即可:dp[i][j] = max(1, dp[i][j])
- 初始化:
由于節點狀態表示與前面題不同,初始化方式也改變,每個節點依賴后一個下位置和右位置節點的值,在 dp 表最后?添加??,并且添加?列后,所有的值都先初始化為?窮?(因為求最小值不能被虛擬節點影響),然后讓dp[m][n - 1] = dp[m - 1][n] = 1 (終點房間所依賴的下一個位置,最小值為1根據題目要求,不然沒法進行下去和其他虛擬節點不同)。
4.填表順序:
發生變化,要從下往上填每??,每??從右往左
- 返回值:
根據狀態表?,需要返回 dp[0][0] 的值
class Solution {
public:int calculateMinimumHP(vector<vector<int>>& d) {int m=d.size(),n=d[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));//特殊初始化dp[m][n-1]=dp[m-1][n]=1;//填表for(int i=m-1;i>=0;i--)//注意下標映射關系沒有變{for(int j=n-1;j>=0;j--){dp[i][j]=min(dp[i+1][j],dp[i][j+1])-d[i][j];dp[i][j]=max(1,dp[i][j]);//防止為負數}}return dp[0][0];}
};