JavaScript網格中的最小路徑講解

Posted on by

問題描述

給你一個下標從 0 開始的整數矩陣 grid ，矩陣大小為 m x n ，由從 0 到 m * n – 1 的不同整數組成。你可以在此矩陣中，從一個單元格移動到 下一行 的任何其他單元格。如果你位於單元格 (x, y) ，且滿足 x < m – 1 ，你可以移動到 (x + 1, 0), (x + 1, 1), …, (x + 1, n – 1) 中的任何一個單元格。註意： 在最後一行中的單元格不能觸發移動。

每次可能的移動都需要付出對應的代價，代價用一個下標從 0 開始的二維數組 moveCost 表示，該數組大小為 (m * n) x n ，其中 moveCost[i][j] 是從值為 i 的單元格移動到下一行第 j 列單元格的代價。從 grid 最後一行的單元格移動的代價可以忽略。

grid 一條路徑的代價是：所有路徑經過的單元格的 值之和 加上 所有移動的 代價之和 。從 第一行 任意單元格出發，返回到達 最後一行 任意單元格的最小路徑代價。

示例 1：

輸入：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
輸出：17
解釋：最小代價的路徑是 5 -> 0 -> 1 。
- 路徑途經單元格值之和 5 + 0 + 1 = 6 。
- 從 5 移動到 0 的代價為 3 。
- 從 0 移動到 1 的代價為 8 。
路徑總代價為 6 + 3 + 8 = 17 。

示例 2：

輸入：grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
輸出：6
解釋：
最小代價的路徑是 2 -> 3 。 
- 路徑途經單元格值之和 2 + 3 = 5 。 
- 從 2 移動到 3 的代價為 1 。 
路徑總代價為 5 + 1 = 6 。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 50
grid 由從 0 到 m * n - 1 的不同整數組成
moveCost.length == m * n
moveCost[i].length == n
1 <= moveCost[i][j] <= 100

思路分析

這道題目其實並不難，難的是對於題目的理解，題目有點長和繞，我們需要仔細閱讀清楚題目給的信息，結合示例一的圖片進行理解會更清晰。

1、題目會給出一個 m * n 的矩陣；

一個下標從 0 開始的整數矩陣 grid ，矩陣大小為 m x n ，由從 0 到 m * n – 1 的不同整數組成。

2、每一行的格子可以移動到下一行的任意一格；

在此矩陣中，從一個單元格移動到 下一行 的任何其他單元格。如果你位於單元格 (x, y) ，且滿足 x < m – 1 ，你可以移動到 (x + 1, 0), (x + 1, 1), …, (x + 1, n – 1) 中的任何一個單元格。

3、moveCost[i][j]表示從值為 i 的單元格移動到下一行第 j 列單元格的代價

每次可能的移動都需要付出對應的代價，代價用一個下標從 0 開始的二維數組 moveCost 表示，該數組大小為 (m * n) x n ，其中 moveCost[i][j] 是從值為 i 的單元格移動到下一行第 j 列單元格的代價。

4、求從 第一行 任意單元格出發，返回到達 最後一行 任意單元格的最小路徑代價。

grid 一條路徑的代價是：所有路徑經過的單元格的 值之和 加上 所有移動的 代價之和 。從 第一行 任意單元格出發，返回到達 最後一行 任意單元格的最小路徑代價。

理清楚上面的這四個信息之後，我們可以發現這是一道經典的dp動態規劃的題目,我們每一個格子的上一步隻能是上一行的某一格，我們隻需要自頂向下求出移動到每一個格子的最下代價即可。

遍歷矩陣的每一個格子，維護上一行到當前格子的最小代價，最後求出最後一行的格子的最小代價即可。

AC代碼

/**
 * @param {number[][]} grid
 * @param {number[][]} moveCost
 * @return {number}
 */
 var minPathCost = function(grid, moveCost) {
    let dp = new Array(grid.length);
    let res = Infinity;
    for(let i = 0; i < dp.length; i++){
        dp[i] = new Array(grid[i].length).fill(0);
        for(let j = 0; j <  dp[i].length; j++){
            if(i === 0) dp[i][j] = grid[i][j];
            else{
                let temp = Infinity;
                for(let k = 0; k < dp[i].length; k++){
                    temp = Math.min(temp,dp[i - 1][k] + moveCost[grid[i - 1][k]][j]);
                }
                dp[i][j] = temp + grid[i][j];
            }
            if(i == grid.length - 1){
                res = Math.min(dp[i][j],res);
            }
        }
    }
    return res;
};

到此這篇關於JavaScript網格中的最小路徑講解的文章就介紹到這瞭,更多相關JS網格內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：