問題描述

給你一個(gè)下標(biāo)從 0 開始的整數(shù)矩陣 grid ，矩陣大小為 m x n ，由從 0 到 m * n - 1 的不同整數(shù)組成。你可以在此矩陣中，從一個(gè)單元格移動(dòng)到 下一行 的任何其他單元格。如果你位于單元格 (x, y) ，且滿足 x < m - 1 ，你可以移動(dòng)到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一個(gè)單元格。注意： 在最后一行中的單元格不能觸發(fā)移動(dòng)。

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

grid 一條路徑的代價(jià)是：所有路徑經(jīng)過的單元格的 值之和 加上 所有移動(dòng)的 代價(jià)之和 。從 第一行 任意單元格出發(fā)，返回到達(dá) 最后一行 任意單元格的最小路徑代價(jià)。

示例 1：

輸入：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
輸出：17
解釋：最小代價(jià)的路徑是 5 -> 0 -> 1 。
- 路徑途經(jīng)單元格值之和 5 + 0 + 1 = 6 。
- 從 5 移動(dòng)到 0 的代價(jià)為 3 。
- 從 0 移動(dòng)到 1 的代價(jià)為 8 。
路徑總代價(jià)為 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
解釋：
最小代價(jià)的路徑是 2 -> 3 。 
- 路徑途經(jīng)單元格值之和 2 + 3 = 5 。 
- 從 2 移動(dòng)到 3 的代價(jià)為 1 。 
路徑總代價(jià)為 5 + 1 = 6 。

提示：

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

思路分析

這道題目其實(shí)并不難，難的是對于題目的理解，題目有點(diǎn)長和繞，我們需要仔細(xì)閱讀清楚題目給的信息，結(jié)合示例一的圖片進(jìn)行理解會更清晰。

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

一個(gè)下標(biāo)從 0 開始的整數(shù)矩陣 grid ，矩陣大小為 m x n ，由從 0 到 m * n - 1 的不同整數(shù)組成。

2、每一行的格子可以移動(dòng)到下一行的任意一格；

在此矩陣中，從一個(gè)單元格移動(dòng)到 下一行 的任何其他單元格。如果你位于單元格 (x, y) ，且滿足 x < m - 1 ，你可以移動(dòng)到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一個(gè)單元格。

3、moveCost[i][j]表示從值為 i 的單元格移動(dòng)到下一行第 j 列單元格的代價(jià)

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

4、求從 第一行 任意單元格出發(fā)，返回到達(dá) 最后一行 任意單元格的最小路徑代價(jià)。

grid 一條路徑的代價(jià)是：所有路徑經(jīng)過的單元格的 值之和 加上 所有移動(dòng)的 代價(jià)之和 。從 第一行 任意單元格出發(fā)，返回到達(dá) 最后一行 任意單元格的最小路徑代價(jià)。

理清楚上面的這四個(gè)信息之后，我們可以發(fā)現(xiàn)這是一道經(jīng)典的dp動(dòng)態(tài)規(guī)劃的題目,我們每一個(gè)格子的上一步只能是上一行的某一格，我們只需要自頂向下求出移動(dòng)到每一個(gè)格子的最下代價(jià)即可。

遍歷矩陣的每一個(gè)格子，維護(hù)上一行到當(dāng)前格子的最小代價(jià)，最后求出最后一行的格子的最小代價(jià)即可。

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;
};

到此這篇關(guān)于JavaScript網(wǎng)格中的最小路徑講解的文章就介紹到這了,更多相關(guān)JS網(wǎng)格內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論