[!info] related notes 动态规划 网格 DP 与双序列 DP

最小路径和

题目链接：https://leetcode.cn/problems/minimum-path-sum/

状态

dp[i][j] 表示从左上角走到 (i, j) 的最小路径和。

转移

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

样例

grid = [[1,3,1],[1,5,1],[4,2,1]]

最优路径和是 7。

JavaScript

var minPathSum = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dp = Array.from({ length: m }, () => new Array(n).fill(0));

    dp[0][0] = grid[0][0];

    for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (let j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    return dp[m - 1][n - 1];
};