??前言

動(dòng)態(tài)規(guī)劃相關(guān)題目都可以參考以下五個(gè)步驟進(jìn)行解答：

1. 狀態(tài)表?

2. 狀態(tài)轉(zhuǎn)移?程

3. 初始化

4. 填表順序

5. 返回值

后面題的解答思路也將按照這五個(gè)步驟進(jìn)行講解。

??下降最小路徑和

??題目描述

給你一個(gè) n x n 的 方形 整數(shù)數(shù)組 matrix ，請(qǐng)你找出并返回通過(guò) matrix 的下降路徑 的 最小和 。

下降路徑 可以從第一行中的任何元素開始，并從每一行中選擇一個(gè)元素。在下一行選擇的元素和當(dāng)前行所選元素最多相隔一列（即位于正下方或者沿對(duì)角線向左或者向右的第一個(gè)元素）。具體來(lái)說(shuō)，位置 (row, col) 的下一個(gè)元素應(yīng)當(dāng)是 (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) {

    }
}

??算法思路：

關(guān)于這?類題，由于我們做過(guò)類似的，因此「狀態(tài)表?」以及「狀態(tài)轉(zhuǎn)移」是?較容易分析出來(lái)的。
?較難的地?可能就是對(duì)于「邊界條件」的處理。

1. 狀態(tài)表?：
   對(duì)于這種「路徑類」的問(wèn)題，我們的狀態(tài)表??般有兩種形式：
   • 從 [i, j] 位置出發(fā)，到達(dá)?標(biāo)位置有多少種?式；
   • 從起始位置出發(fā)，到達(dá) [i, j] 位置，?共有多少種?式

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

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

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

4. 填表順序：
   根據(jù)「狀態(tài)表?」，填表的順序是「從上往下」。

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

題?要求「只要到達(dá)最后??」就?了，因此這?應(yīng)該返回「dp表中最后??的最?值」。

??代碼實(shí)現(xiàn)

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        // 1. 創(chuàng)建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回結(jié)果
        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;
    }
}

??最小路徑和

給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說(shuō)明：每次只能向下或者向右移動(dòng)一步。

• 示例 1：
  
  輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
  輸出：7
  解釋：因?yàn)槁窂?1→3→1→1→1 的總和最小。

• 示例 2：
  輸入：grid = [[1,2,3],[4,5,6]]
  輸出：12

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

    }
}

??算法思路

像這種表格形式的動(dòng)態(tài)規(guī)劃，是?常容易得到「狀態(tài)表?」以及「狀態(tài)轉(zhuǎn)移?程」的，可以歸結(jié)到「不同路徑」?類的題??。

1. 狀態(tài)表?：
   對(duì)于這種路徑類的問(wèn)題，我們的狀態(tài)表??般有兩種形式：
   • 從 [i, j] 位置出發(fā)，一系列操作；
   • 從起始位置出發(fā)，到達(dá) [i, j] 位置，一系列操作。

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

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

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

3. 初始化：
   可以在最前?加上?個(gè)「輔助結(jié)點(diǎn)」，幫助我們初始化。使?這種技巧要注意兩個(gè)點(diǎn)：
   • 輔助結(jié)點(diǎn)??的值要「保證后續(xù)填表是正確的」；
   • 「下標(biāo)的映射關(guān)系」。

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

4. 填表順序：
   根據(jù)「狀態(tài)轉(zhuǎn)移?程」的推導(dǎo)來(lái)看，填表的順序就是「從上往下」填每??，每??「從左往后」。

5. 返回值：
   根據(jù)「狀態(tài)表?」，我們要返回的結(jié)果是 dp[m][n]

??代碼實(shí)現(xiàn)

class Solution {
    public int minPathSum(int[][] grid) {
        // 1. 創(chuàng)建 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];
    }
}

??地下城游戲

??題目描述

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

騎士的初始健康點(diǎn)數(shù)為一個(gè)正整數(shù)。如果他的健康點(diǎn)數(shù)在某一時(shí)刻降至 0 或以下，他會(huì)立即死亡。

有些房間由惡魔守衛(wèi)，因此騎士在進(jìn)入這些房間時(shí)會(huì)失去健康點(diǎn)數(shù)（若房間里的值為負(fù)整數(shù)，則表示騎士將損失健康點(diǎn)數(shù)）；其他房間要么是空的（房間里的值為 0），要么包含增加騎士健康點(diǎn)數(shù)的魔法球（若房間里的值為正整數(shù)，則表示騎士將增加健康點(diǎn)數(shù)）。

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

返回確保騎士能夠拯救到公主所需的最低初始健康點(diǎn)數(shù)。

注意：任何房間都可能對(duì)騎士的健康點(diǎn)數(shù)造成威脅，也可能增加騎士的健康點(diǎn)數(shù)，包括騎士進(jìn)入的左上角房間以及公主被監(jiān)禁的右下角房間。

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

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

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

    }
}

??算法思路

1. 狀態(tài)表?：

這道題如果我們定義成：從起點(diǎn)開始，到達(dá) [i, j] 位置的時(shí)候，所需的最低初始健康點(diǎn)數(shù)。那么我們分析狀態(tài)轉(zhuǎn)移的時(shí)候會(huì)有?個(gè)問(wèn)題：那就是我們當(dāng)前的健康點(diǎn)數(shù)還會(huì)受到后?的路徑的影響。也就是從上往下的狀態(tài)轉(zhuǎn)移不能很好地解決問(wèn)題。

這個(gè)時(shí)候我們要換?種狀態(tài)表?：從 [i, j] 位置出發(fā)，到達(dá)終點(diǎn)時(shí)所需要的最低初始健康點(diǎn)數(shù)。這樣我們?cè)诜治鰻顟B(tài)轉(zhuǎn)移的時(shí)候，后續(xù)的最佳狀態(tài)就已經(jīng)知曉。

綜上所述，定義狀態(tài)表?為：
dp[i][j] 表?：從 [i, j] 位置出發(fā)，到達(dá)終點(diǎn)時(shí)所需的最低初始健康點(diǎn)數(shù)。

2. 狀態(tài)轉(zhuǎn)移?程：
   對(duì)于 dp[i][j] ，從 [i, j] 位置出發(fā)，下?步會(huì)有兩種選擇（為了?便理解，設(shè) dp[i] [j] 的最終答案是 x ）：
   • ?到右邊，然后?向終點(diǎn)
     那么我們?cè)?[i, j] 位置的最低健康點(diǎn)數(shù)加上這?個(gè)位置的消耗，應(yīng)該要?于等于右邊位置的最低健康點(diǎn)數(shù)，也就是： x + dungeon[i][j] >= dp[i][j + 1] 。通過(guò)移項(xiàng)可得： x >= dp[i][j + 1] - dungeon[i][j] 。因?yàn)槲覀円氖亲?值，因此這種情況下的 x = dp[i][j + 1] - dungeon[i][j] ；
   • ?到下邊，然后?向終點(diǎn)
     那么我們?cè)?[i, j] 位置的最低健康點(diǎn)數(shù)加上這?個(gè)位置的消耗，應(yīng)該要?于等于下邊位置的最低健康點(diǎn)數(shù)，也就是： x + dungeon[i][j] >= dp[i + 1][j] 。通過(guò)移項(xiàng)可得： x >= dp[i + 1][j] - dungeon[i][j] 。因?yàn)槲覀円氖亲?值，因此這種情況下的 x = dp[i + 1][j] - dungeon[i][j] ；

綜上所述，我們需要的是兩種情況下的最?值，因此可得狀態(tài)轉(zhuǎn)移?程為：dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]

但是，如果當(dāng)前位置的 dungeon[i][j] 是?個(gè)?較?的正數(shù)的話， dp[i][j] 的值可能變成 0 或者負(fù)數(shù)。也就是最低點(diǎn)數(shù)會(huì)?于 1 ，那么騎?就會(huì)死亡。因此我們求出來(lái)的 dp[i][j] 如果?于等于 0 的話，說(shuō)明此時(shí)的最低初始值應(yīng)該為 1 。處理這種情況僅需讓 dp[i][j] 與 1 取?個(gè)最?值即可：dp[i][j] = max(1, dp[i][j])

3. 初始化：
   可以在最前?加上?個(gè)「輔助結(jié)點(diǎn)」，幫助我們初始化。使?這種技巧要注意兩個(gè)點(diǎn)：
   • 輔助結(jié)點(diǎn)??的值要「保證后續(xù)填表是正確的」；
   • 「下標(biāo)的映射關(guān)系」。

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

4. 填表順序：
   根據(jù)「狀態(tài)轉(zhuǎn)移?程」，我們需要「從下往上填每??」，「每??從右往左」。

5. 返回值：
   根據(jù)「狀態(tài)表?」，我們需要返回 dp[0][0] 的值

??代碼實(shí)現(xiàn)

class Solution {
    public int calculateMinimumHP(int[][] d) {
        // 1. 創(chuàng)建 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];
    }
}

?總結(jié)

關(guān)于《【算法優(yōu)選】 動(dòng)態(tài)規(guī)劃之路徑問(wèn)題——貳》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評(píng)指正，如果文章對(duì)您有幫助或者覺(jué)得作者寫的還不錯(cuò)可以點(diǎn)一下關(guān)注，點(diǎn)贊，收藏支持一下！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-751835.html

到了這里，關(guān)于【算法優(yōu)選】 動(dòng)態(tài)規(guī)劃之路徑問(wèn)題——貳的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！