JavaScript網格中的最小路徑怎么實現

這篇“JavaScript網格中的最小路徑怎么實現”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“JavaScript網格中的最小路徑怎么實現”文章吧。

問題描述

給你一個下標從 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網格中的最小路徑怎么實現”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。