【動態規劃算法】路徑問題

什么是動態規劃算法

動態規劃(Dynamic Programming,簡稱 DP)是一種通過分解復雜問題為重疊子問題,并存儲子問題的解以避免重復計算,從而高效求解具有特定性質(重疊子問題、最優子結構)問題的算法思想。

一、核心思想:“分解 + 復用”

動態規劃的核心在于:
1.將原問題拆解為規模更小的子問題;
2.求解子問題后,將結果存儲起來(記憶化),避免后續重復計算;
3.基于子問題的解,推導出原問題的解。
簡單來說,就是 “用已知的子問題答案,解決未知的大問題”,本質是用空間換時間。

二、動態規劃的 2 個關鍵前提

只有當問題滿足以下兩個條件時,才能用動態規劃求解:

  1. 重疊子問題
    問題可以分解為多個重復出現的子問題。
    例如:計算斐波那契數列 f(n) = f(n-1) + f(n-2) 時,f(5) 依賴 f(4) 和 f(3),f(4) 又依賴 f(3) 和 f(2)——f(3) 就是被重復計算的重疊子問題。
  2. 最優子結構(Optimal Substructure)
    問題的最優解包含子問題的最優解。
    例如:求 “從 A 到 B 的最短路徑” 時,若路徑 A→C→B 是最優解,則 A→C 和 C→B 一定分別是 A 到 C、C 到 B 的最短路徑(子問題的最優解)。

三、動態規劃的 2 種實現方式

動態規劃通常有兩種實現思路,核心都是 “存儲子問題的解”,只是順序不同:

  1. 自頂向下(Top-Down):遞歸 + 記憶化
    思路:從原問題出發,遞歸分解為子問題,用備忘錄(數組或哈希表) 存儲已求解的子問題答案,避免重復計算。
  2. 自底向上(Bottom-Up):迭代 + DP 表
    思路:從最小的子問題開始,按順序求解,用DP 表(數組) 記錄子問題的解,逐步推導出原問題的解。

四、經典應用場景

動態規劃廣泛用于求解 “最優問題” 或 “計數問題”,典型案例包括:
計數問題:爬樓梯(方法數)、不同路徑(網格中路徑數);
最優問題:最長公共子序列(LCS)、最大子數組和、0-1 背包問題(最大價值);
其他:編輯距離(字符串相似度)、打家劫舍(不相鄰房屋最大金額)等。

五、動態規劃與其他算法的區別

與遞歸:遞歸可能重復計算子問題,動態規劃通過記憶化避免重復,效率更高;
與貪心算法:貪心只做局部最優選擇,不依賴子問題的解;動態規劃則基于子問題的最優解推導全局最優;
與分治法:分治法(如歸并排序)的子問題不重疊,無需存儲解;動態規劃的子問題重疊,必須存儲解。

一. (62.)不同路徑(力扣)

在這里插入圖片描述

1.1算法原理

  1. 狀態表?:

對于這種「路徑類」的問題,我們的狀態表??般有兩種形式:
i. 從 [i, j] 位置出發,巴拉巴拉;
ii. 從起始位置出發,到達 [i, j] 位置,巴拉巴拉。
這?選擇第?種定義狀態表?的?式:
dp[i][j] 表?:?到 [i, j] 位置處,?共有多少種?式。

  1. 狀態轉移?程:

從最近的一步將問題劃分為子問題,再由若干個子問題來來解決總問題。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,就不會影響后續填表

  1. 填表順序:

根據狀態轉移?程的推導來看,填表的順序就是從上往下填每??,在填寫每??的時候從左往右。

  1. 返回值:

根據狀態表?,由于多增加了一行一列的虛擬節點,我們要返回 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算法原理

  1. 狀態表示:

dp[i][j] 表?:?到 [i, j] 位置處,?共有多少種?式。

  1. 狀態轉移:

到達 [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,就不會影響后續填表

  1. 填表順序:

根據狀態轉移?程的推導來看,填表的順序就是從上往下填每??,在填寫每??的時候從左往右。

  1. 返回值:

根據狀態表?,由于多增加了一行一列的虛擬節點,我們要返回 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] 位置處,此時的最?價值。

  1. 狀態轉移?程:

對于 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表與原數組下標的映射關系

  1. 填表順序:
    從上往下填寫每??,每??從左往右。

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算法原理

  1. 狀態表?

dp[i][j] 表?:到達 [i, j] 位置時,所有下降路徑中的最?和。

  1. 狀態轉移?程:

對于普遍位置 [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

  1. 填表順序:

從上往下

  1. 返回值:

注意這?不是返回 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算法原理

  1. 狀態表?:

dp[i][j] 表?:到達 [i, j] 位置處,最?路徑和是多少。

  1. 狀態轉移:

表?到達 到達 [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]

  1. 初始化:

在這里插入圖片描述

添加??,并且添加?列后,所有位置的值可以初始化為?窮?,然后讓
dp[0][1] = dp[1][0] = 1 即可。(因為求的是最小值,不能讓虛擬節點干擾)

  1. 填表順序:從上往下填每??,每??從左往后
  2. 由于多加了一行一列的虛擬節點,返回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算法原理

  1. 狀態表?:

這道題如果我們定義成:從起點開始,到達 [i, j] 位置的時候,所需的最低初始健康點數。那么我們分析狀態轉移的時候會有?個問題:那就是我們當前的健康點數還會受到后?的路徑的影響。也就是從上往下的狀態轉移不能很好地解決問題。
這個時候我們要換?種狀態表?:從 [i, j] 位置出發,到達終點時所需要的最低初始健康點數。這樣我們在分析狀態轉移的時候,后續的最佳狀態就已經知曉。
綜上所述,定義狀態表?為:
dp[i][j] 表?:從 [i, j] 位置出發,到達終點時所需的最低初始健康點數

  1. 狀態轉移?程:

在這里插入圖片描述
在 [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])

  1. 初始化:

由于節點狀態表示與前面題不同,初始化方式也改變,每個節點依賴后一個下位置和右位置節點的值,在 dp 表最后?添加??,并且添加?列后,所有的值都先初始化為?窮?(因為求最小值不能被虛擬節點影響),然后讓dp[m][n - 1] = dp[m - 1][n] = 1 (終點房間所依賴的下一個位置,最小值為1根據題目要求,不然沒法進行下去和其他虛擬節點不同)。

4.填表順序:

發生變化,要從下往上填每??,每??從右往左

  1. 返回值:

根據狀態表?,需要返回 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];}
};

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/pingmian/91715.shtml
繁體地址,請注明出處:http://hk.pswp.cn/pingmian/91715.shtml
英文地址,請注明出處:http://en.pswp.cn/pingmian/91715.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Java基本技術講解

一、基礎語法三要素 暫時無法在飛書文檔外展示此內容 &#x1f511; 黃金法則?&#xff1a;每個變量都要聲明類型&#xff01;二、程序邏輯控制&#xff08;游戲行為核心&#xff09; 條件判斷&#xff1a;if-else - “岔路口選擇” // 撿到金幣邏輯 if (isTouching(Coin.clas…

【網絡基礎2】路由器的 “兩扇門”:二層接口和三層接口到底有啥不一樣?

目錄 前言:路由器不是只有 “插網線的口” 一、先搞懂一個基礎:路由器是 “網絡交通樞紐” 二、二層接口:“小區內部的單元門”,只認 “住戶身份證” 1. 啥是二層接口? 2. 用 “小區內部串門” 理解二層接口 步驟 1:手機打包數據,寫上 “收件人身份證” 步驟 2:二…

MLIR TableGen

簡介 TableGen 是一種領域特定語言&#xff08;DSL&#xff09;&#xff0c;TableGen 的設計目標是允許編寫靈活的描述&#xff0c;并將記錄的通用特性提取出來&#xff0c;從而減少重復代碼并提高代碼的可維護性。 TableGen的工作流程&#xff1a; 前端解析&#xff1a; Ta…

2、docker容器命令 | 信息查看

1、命令總覽命令作用docker ps查看運行中的容器&#xff08;-a查看所有容器&#xff09;docker logs [CONTAINER]查看容器日志&#xff08;-f實時追蹤日志&#xff09;docker inspect [CONTAINER]查看容器詳細信息&#xff08;JSON格式&#xff09;docker stats [CONTAINER]實時…

【MySQL】MySQL中鎖有哪些?

一、按照粒度分類&#xff1a; 粒度越小&#xff0c;并發度越高&#xff0c;鎖開銷越大。 1.全局鎖&#xff1a; 作用&#xff1a; 鎖定整個MySQL實例(所有數據庫)。適用場景&#xff1a; 全庫邏輯部分。(確保備份期間數據的一致性。)實現方式&#xff1a; 通過 FLUSH TABLES W…

語義分割--deeplabV3+

根據論文網絡結構圖講一下&#xff1a;網絡分為兩部分&#xff1a;encoder和decoder部分。 Encoder&#xff1a;DCNN就是主干網絡&#xff0c;例如resnet&#xff0c;Xception&#xff0c;MobileNet這些&#xff08;主干網絡也要使用空洞卷積&#xff09;&#xff0c;對dcnn的結…

Azure DevOps 中的代理

必知詞匯 深入研究 Azure DevOps 中的代理之前需要掌握的基本概念: 代理:Azure DevOps 中的代理是一個軟件組件,負責執行流水線中的任務和作業。這可能包括數據中心內的物理服務器、本地或云端托管的虛擬機,甚至是容器化環境。這些代理可以在各種操作系統和環境中運行,例如…

AUTOSAR進階圖解==>AUTOSAR_SRS_ADCDriver

AUTOSAR ADC驅動詳解 基于AUTOSAR標準的ADC驅動模塊需求規范分析目錄 ADC驅動模塊概述 關鍵概念定義 ADC驅動架構 ADC驅動在AUTOSAR分層架構中的位置ADC驅動的主要職責 ADC驅動配置結構 通用配置(AdcGeneral)硬件單元配置(AdcHwUnit)通道配置(AdcChannel)通道組配置(AdcChanne…

寶馬集團與SAP聯合打造生產物流數字化新標桿

在德國雷根斯堡的寶馬工廠&#xff0c;每57秒就有一輛新車下線。這座工廠不僅是汽車制造的基地&#xff0c;更是寶馬集團向SAP S/4HANA云平臺轉型的先鋒項目。通過“RISE with SAP”計劃&#xff0c;寶馬將該工廠的運營系統全面遷移至SAP S/4HANA Cloud Private Edition&#x…

Go 語言實戰:構建一個高性能的 MySQL + Redis 應用

引言&#xff1a;為什么是 Go MySQL Redis&#xff1f;在現代后端技術棧中&#xff0c;Go MySQL Redis 的組合堪稱“黃金搭檔”&#xff0c;被廣泛應用于各種高并發業務場景。Go 語言&#xff1a;以其卓越的并發性能、簡潔的語法和高效的執行效率&#xff0c;成為構建高性能…

Excel超級處理器,多個word表格模板中內容提取到Excel表格中

在職場中&#xff0c;很多人習慣在word里插入表格&#xff0c;設計模板&#xff0c;填寫內容&#xff0c;一旦有多個word文件需要整理在excel表格中&#xff0c;最常見的工作方式就是每個word文件打開&#xff0c;復制&#xff0c;粘貼到excel表格里&#xff0c;這樣的工作方式…

前端工程化:ES6特性

本文為個人學習筆記整理&#xff0c;僅供交流參考&#xff0c;非專業教學資料&#xff0c;內容請自行甄別 文章目錄一、let與var1.1、越獄問題1.2、變量的重復聲明1.3、變量提升問題二、解構2.1、數組解構2.2、對象解構2.3、方法解構三、鏈判斷四、參數默認值五、箭頭函數六、模…

大屏項目展示

一、項目克隆與基礎操作 我們參考的項目 互聯網設備可視化平臺---IofTV-Screen: ??一個基于 vue、datav、Echart 框架的物聯網可視化(大屏展示)模板,提供數據動態刷新渲染、屏幕適應、數據滾動配置,內部圖表自由替換、Mixins注入等功能,持續更新.... 將次項目克隆到本…

基于R語言地理加權回歸、主成份分析、判別分析等空間異質性數據分析實踐技術應用

在自然和社會科學領域有大量與地理或空間有關的數據&#xff0c;這一類數據一般具有嚴重的空間異質性&#xff0c;而通常的統計學方法并不能處理空間異質性&#xff0c;因而對此類型的數據無能為力。以地理加權回歸為基礎的一系列方法&#xff1a;經典地理加權回歸&#xff0c;…

【Flask 基礎 ①】 | 路由、參數與模板渲染

0 序言 Flask 是 Python 生態中一款輕量級 Web 框架&#xff0c;以簡潔、靈活著稱。 學習 Flask 的意義在于&#xff1a; 快速開發&#xff1a;通過少量代碼即可搭建功能完整的 Web 應用&#xff1b;理解原理&#xff1a;其設計清晰體現了 Web 框架的核心邏輯&#xff0c;如路由…

wordpress登陸前登陸后顯示不同的頂部菜單

在WordPress中讓“未登錄”和“已登錄”用戶看到不同的頂部菜單&#xff0c;最干凈、最安全、最可維護的做法是&#xff1a; 在同一個菜單位置(themelocation)里&#xff0c;根據is_user_logged_in()動態切換菜單。 下面給出三種常見實現方式&#xff0c;按推薦程度排序。任選…

【昇騰推理PaddleOCR】生產級部署方式

已知的在昇騰上推理Paddle OCR有三種方法&#xff1a; 概要&#xff1a; PyTorch官方提供了昇騰插件包&#xff0c;安裝后雖然可以支持PytorchOCR和PaddlePaddle的推理任務&#xff0c;但性能較低。換句話說&#xff0c;PaddlePaddle框架層面支持了昇騰&#xff0c;但具體到某個…

LangChain摘要記憶組件的使用與解析

01. 摘要記憶組件的類型 在 LangChain 中使用緩沖記憶組件要不就保存所有信息&#xff08;占用過多容量&#xff09;&#xff0c;要不就保留最近的記憶信息&#xff08;丟失太多重要信息&#xff09;&#xff0c;那么有沒有一種情況是既要又要呢&#xff1f; 所以折中方案就出…

NAT與智能選路

1、NAT 基礎概念核心作用&#xff1a;私網地址無法在 Internet 上直接使用和分配&#xff0c;NAT 通過將私有地址與公有地址及端口進行轉換&#xff0c;實現私網與公網的通信。轉換示例&#xff1a;內網用戶&#xff08;10.1.1.1&#xff09;訪問外網 FTP Server&#xff08;12…

【05】VisionMaster入門到精通——圓查找

文章目錄1 運行參數先檢測出多個邊緣點然后擬合成圓形&#xff0c;可用于圓的定位與測量 1 運行參數 先檢測出多個邊緣點然后擬合成圓形&#xff0c;可用于圓的定位與測量——運行參數 扇環半徑——圓環ROI的內外圓半經&#xff1b; 邊綠類型 最強——只檢測掃描范圍內梯度最…