JavaScript实现网格最小路径代价：动态规划详解

阿麦

发布时间：2026-10-15 | 5人浏览过

原创

在二维网格中寻找从第一行到最后一行的最小路径代价，关键在于理解移动规则并应用动态规划算法。本文将使用JavaScript实现该逻辑，详细解析如何结合单元格数值与移动代价计算最优路径。

结果与目标

给定一个 m x n 的整数矩阵 grid 和一个表示移动代价的二维数组 moveCost。我们需要找到一条从第一行任意单元格出发，到达最后一行任意单元格的路径，使得以下总和最小：

路径经过的所有单元格的值之和；
所有相邻单元格之间移动的代价之和。

准备条件

输入参数定义：

grid: m x n 的二维数组，元素为互不相同的整数。m 为行数，n 为列数。
moveCost: 大小为 (m * n) x n 的二维数组。其中 moveCost[i][j] 表示从值为 i 的单元格移动到下一行第 j 列单元格的代价。

约束条件：

2 <= m, n <= 50
1 <= moveCost[i][j] <= 100
位于 (x, y) 的单元格可以移动到下一行的任何一列 (x + 1, k)，其中 0 <= k < n。

真实操作顺序（算法实现）

第1步：初始化动态规划数组

创建一个与 grid 维度相同的二维数组 dp，用于存储到达每个格子的最小累积代价。初始时所有值设为 0。

let dp = new Array(grid.length);
for(let i = 0; i < dp.length; i++){
    dp[i] = new Array(grid[i].length).fill(0);
}

第2步：处理第一行基准状态

对于第一行（i = 0）的每个单元格，到达它的最小代价就是其自身的值，因为还没有产生移动代价。即：dp[0][j] = grid[0][j]。

第3步：逐行计算最小累积代价

从第二行开始（i = 1 到 m-1），遍历每一行的每一列 j。对于当前格子 (i, j)，其值来自上一行某一列 k 的移动。我们需要检查上一行所有可能的来源，找出最小代价：

遍历上一行的每一列 k。
计算从上一行 k 列移动到当前 j 列的总代价：dp[i-1][k] + moveCost[grid[i-1][k]][j]。
取这些可能性的最小值作为到达当前格子的基础移动代价。
加上当前格子的值 grid[i][j]，得到最终的 dp[i][j]。

// 伪代码逻辑
for(i from 1 to m-1):
    for(j from 0 to n-1):
        minPrev = Infinity
        for(k from 0 to n-1): // 遍历上一行所有列
             cost = dp[i-1][k] + moveCost[grid[i-1][k]][j]
             if cost < minPrev: minPrev = cost
        dp[i][j] = minPrev + grid[i][j]

第4步：获取最终结果

遍历完最后一行后，dp[m-1] 中的最小值即为整个网格的最小路径代价。

示例演示

以示例 1 为例，观察路径的计算过程：

输入：grid = [[5,3],[4,0],[2,1]], moveCost = ...

第一行：代价分别为 5, 3。
第二行：
- 到达 (1,0) 值为 4：从上一行 5 移来代价 9+4=13；从 3 移来代价... 取最小。
- 到达 (1,1) 值为 0：同理计算最小前驱代价。
第三行：继续向上累加。最终路径 5->0->1 的总代价为 17（单元格值和 6 + 移动代价 11）。注：原题解中移动代价拆分说明为 3+8=11，加上节点值 5+0+1=6，总计 17。

JavaScript AC 代码实现

以下是完整的 JavaScript 函数实现，可直接用于解题环境（如 LeetCode）：

/**
 * @param {number[][]} grid
 * @param {number[][]} moveCost
 * @return {number}
 */
var minPathCost = function(grid, moveCost) {
    let rows = grid.length;
    let cols = grid[0].length;
    
    // 初始化 DP 表
    let dp = new Array(rows);
    for(let i = 0; i < rows; i++){
        dp[i] = new Array(cols).fill(0);
    }
    
    // 填充 DP 表
    for(let i = 0; i < rows; i++){
        for(let j = 0; j < cols; j++){
            if(i === 0) {
                // 第一行直接填值
                dp[i][j] = grid[i][j];
            } else {
                // 寻找上一行到当前位置的最小代价
                let tempMin = Infinity;
                for(let k = 0; k < cols; k++) {
                    // 上一步的值是 grid[i-1][k]
                    // 移动到当前列 j 的代价是 moveCost[grid[i-1][k]][j]
                    let currentStepCost = dp[i - 1][k] + moveCost[grid[i - 1][k]][j];
                    if(currentStepCost < tempMin) {
                        tempMin = currentStepCost;
                    }
                }
                dp[i][j] = tempMin + grid[i][j];
            }
        }
    }
    
    // 返回最后一行的最小值
    return Math.min(...dp[rows - 1]);
};