🎋前言

動態規劃相關題目都可以參考以下五個步驟進行解答：

1. 狀態表?

2. 狀態轉移?程

3. 初始化

4. 填表順序

5. 返回值

后面題的解答思路也將按照這五個步驟進行講解。

🌲下降最小路徑和

🚩題目描述

給你一個 n x n 的 方形 整數數組 matrix ，請你找出并返回通過 matrix 的下降路徑 的 最小和 。

下降路徑 可以從第一行中的任何元素開始，并從每一行中選擇一個元素。在下一行選擇的元素和當前行所選元素最多相隔一列（即位于正下方或者沿對角線向左或者向右的第一個元素）。具體來說，位置 (row, col) 的下一個元素應當是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

• 示例 1：

輸入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
輸出：13
解釋：如圖所示，為和最小的兩條下降路徑

• 示例 2：

輸入：matrix = [[-19,57],[-40,-5]]
輸出：-59
解釋：如圖所示，為和最小的下降路徑

class Solution {public int minFallingPathSum(int[][] matrix) {}
}

🚩算法思路：

關于這?類題，由于我們做過類似的，因此「狀態表?」以及「狀態轉移」是?較容易分析出來的。
?較難的地?可能就是對于「邊界條件」的處理。

1. 狀態表?：
   對于這種「路徑類」的問題，我們的狀態表??般有兩種形式：
   • 從 [i, j] 位置出發，到達?標位置有多少種?式；
   • 從起始位置出發，到達 [i, j] 位置，?共有多少種?式

這?選擇第?種定義狀態表?的?式：
dp[i][j] 表?：到達 [i, j] 位置時，所有下降路徑中的最?和。

2. 狀態轉移?程：
   對于普遍位置 [i, j] ，根據題意得，到達 [i, j] 位置可能有三種情況：
   • 從正上? [i - 1, j] 位置轉移到 [i, j] 位置；
   • 從左上? [i - 1, j - 1] 位置轉移到 [i, j] 位置；
   • 從右上? [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. 初始化：
   可以在最前?加上?個「輔助結點」，幫助我們初始化。使?這種技巧要注意兩個點：
   • 輔助結點??的值要「保證后續填表是正確的」；
   • 「下標的映射關系」。

在本題中，需要「加上??」，并且「加上兩列」。所有的位置都初始化為?窮?，然后將第??初始化為0 即可。

4. 填表順序：
   根據「狀態表?」，填表的順序是「從上往下」。

5. 返回值：
   注意這?不是返回 dp[m][n] 的值！

題?要求「只要到達最后??」就?了，因此這?應該返回「dp表中最后??的最?值」。

🚩代碼實現

class Solution {public int minFallingPathSum(int[][] matrix) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回結果int n = matrix.length;int[][] dp = new int[n + 1][n + 2];for(int i = 1; i <= n; i++) {dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++) {dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1],dp[i - 1][j + 1])) + matrix[i - 1][j - 1];}}int ret = Integer.MAX_VALUE;for(int j = 1; j <= n; j++) {ret = Math.min(ret, dp[n][j]);}return ret;}
}

🎍最小路徑和

class Solution {public int minPathSum(int[][] grid) {}
}

🚩算法思路

像這種表格形式的動態規劃，是?常容易得到「狀態表?」以及「狀態轉移?程」的，可以歸結到「不同路徑」?類的題??。

1. 狀態表?：
   對于這種路徑類的問題，我們的狀態表??般有兩種形式：
   • 從 [i, j] 位置出發，一系列操作；
   • 從起始位置出發，到達 [i, j] 位置，一系列操作。

這?選擇第?種定義狀態表?的?式：dp[i][j] 表?：到達 [i, j] 位置處，最?路徑和是多少。

2. 狀態轉移：
   簡單分析?下。如果 dp[i][j] 表?到達到達 [i, j] 位置處的最?路徑和，那么到達[i, j] 位置之前的??步，有兩種情況：
   • 從 [i - 1, j] 向下??步，轉移到 [i, j] 位置；
   • 從 [i, j - 1] 向右??步，轉移到 [i, j] 位置。

由于到 [i, j] 位置兩種情況，并且我們要找的是最?路徑，因此只需要這兩種情況下的最?值，再加上 [i, j] 位置上本?的值即可。也就是： dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

3. 初始化：
   可以在最前?加上?個「輔助結點」，幫助我們初始化。使?這種技巧要注意兩個點：
   • 輔助結點??的值要「保證后續填表是正確的」；
   • 「下標的映射關系」。

在本題中，「添加??」，并且「添加?列」后，所有位置的值可以初始化為?窮?，然后讓dp[0][1] = dp[1][0] = 1 即可。

4. 填表順序：
   根據「狀態轉移?程」的推導來看，填表的順序就是「從上往下」填每??，每??「從左往后」。

5. 返回值：
   根據「狀態表?」，我們要返回的結果是 dp[m][n]

🚩代碼實現

class Solution {public int minPathSum(int[][] grid) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m = grid.length;int n = grid[0].length;int[][] dp = new int[m + 1][n + 1];for(int j = 0; j <= n; j++)  {dp[0][j] = Integer.MAX_VALUE;}for(int i = 0; i <= m; i++) {dp[i][0] = Integer.MAX_VALUE;}dp[0][1] = dp[1][0] = 0;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++) {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j-1];}}return dp[m][n];}
}

🌴地下城游戲

🚩題目描述

惡魔們抓住了公主并將她關在了地下城 dungeon 的 右下角 。地下城是由 m x n 個房間組成的二維網格。我們英勇的騎士最初被安置在 左上角 的房間里，他必須穿過地下城并通過對抗惡魔來拯救公主。

騎士的初始健康點數為一個正整數。如果他的健康點數在某一時刻降至 0 或以下，他會立即死亡。

有些房間由惡魔守衛，因此騎士在進入這些房間時會失去健康點數（若房間里的值為負整數，則表示騎士將損失健康點數）；其他房間要么是空的（房間里的值為 0），要么包含增加騎士健康點數的魔法球（若房間里的值為正整數，則表示騎士將增加健康點數）。

為了盡快解救公主，騎士決定每次只 向右 或 向下 移動一步。

返回確保騎士能夠拯救到公主所需的最低初始健康點數。

注意：任何房間都可能對騎士的健康點數造成威脅，也可能增加騎士的健康點數，包括騎士進入的左上角房間以及公主被監禁的右下角房間。

• 示例 1：
  
  輸入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
  輸出：7
  解釋：如果騎士遵循最佳路徑：右 -> 右 -> 下 -> 下 ，則騎士的初始健康點數至少為 7 。

• 示例 2：
  輸入：dungeon = [[0]]
  輸出：1

class Solution {public int calculateMinimumHP(int[][] dungeon) {}
}

🚩算法思路

1. 狀態表?：

這道題如果我們定義成：從起點開始，到達 [i, j] 位置的時候，所需的最低初始健康點數。那么我們分析狀態轉移的時候會有?個問題：那就是我們當前的健康點數還會受到后?的路徑的影響。也就是從上往下的狀態轉移不能很好地解決問題。

這個時候我們要換?種狀態表?：從 [i, j] 位置出發，到達終點時所需要的最低初始健康點數。這樣我們在分析狀態轉移的時候，后續的最佳狀態就已經知曉。

綜上所述，定義狀態表?為：
dp[i][j] 表?：從 [i, j] 位置出發，到達終點時所需的最低初始健康點數。

2. 狀態轉移?程：
   對于 dp[i][j] ，從 [i, j] 位置出發，下?步會有兩種選擇（為了?便理解，設 dp[i] [j] 的最終答案是 x ）：
   • ?到右邊，然后?向終點
     那么我們在 [i, j] 位置的最低健康點數加上這?個位置的消耗，應該要?于等于右邊位置的最低健康點數，也就是： x + dungeon[i][j] >= dp[i][j + 1] 。通過移項可得： x >= dp[i][j + 1] - dungeon[i][j] 。因為我們要的是最?值，因此這種情況下的 x = dp[i][j + 1] - dungeon[i][j] ；
   • ?到下邊，然后?向終點
     那么我們在 [i, j] 位置的最低健康點數加上這?個位置的消耗，應該要?于等于下邊位置的最低健康點數，也就是： x + dungeon[i][j] >= dp[i + 1][j] 。通過移項可得： x >= dp[i + 1][j] - dungeon[i][j] 。因為我們要的是最?值，因此這種情況下的 x = dp[i + 1][j] - dungeon[i][j] ；

綜上所述，我們需要的是兩種情況下的最?值，因此可得狀態轉移?程為：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])

3. 初始化：
   可以在最前?加上?個「輔助結點」，幫助我們初始化。使?這種技巧要注意兩個點：
   • 輔助結點??的值要「保證后續填表是正確的」；
   • 「下標的映射關系」。

在本題中，在 dp 表最后?添加??，并且添加?列后，所有的值都先初始化為?窮?，然后讓dp[m][n - 1] = dp[m - 1][n] = 1 即可。

4. 填表順序：
   根據「狀態轉移?程」，我們需要「從下往上填每??」，「每??從右往左」。

5. 返回值：
   根據「狀態表?」，我們需要返回 dp[0][0] 的值

🚩代碼實現

class Solution {public int calculateMinimumHP(int[][] d) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m = d.length;int n = d[0].length;int[][] dp = new int[m + 1][n + 1];for(int j = 0; j <= n; j++) {dp[m][j] = Integer.MAX_VALUE;}for(int i = 0; i <= m; i++) {dp[i][n] = Integer.MAX_VALUE;}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] = Math.min(dp[i][j + 1], dp[i + 1][j]) - d[i][j];dp[i][j] = Math.max(dp[i][j], 1);}}return dp[0][0];}
}

?總結

關于《【算法優選】 動態規劃之路徑問題——貳》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評指正，如果文章對您有幫助或者覺得作者寫的還不錯可以點一下關注，點贊，收藏支持一下！