最小路径和

最小路径和

这道题跟三角形最小路径和类似

题目描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例：

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

思想

这是一道二维数组的动态规划题目， 左边表示输入， 右边表示dp 结果集

• 第一行只能够向右走， 所以 dp[i][j] = grid[i][j] + dp[i][j - 1];
• 第一列只能向下走，所以 dp[i][j] = grid[i][j] + dp[i - 1][j]
• 其余符合 dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);

w

输入

i / k	k = 0	k = 1	k = 2
i = 0	1	3	1
i = 1	1	5	1
i = 2	4	2	1

dp结果集

i / k	k = 0	k = 1	k = 2
i = 0	1	4	5
i = 1	2	7 (上面dp值与左边dp值比较取最小 + grid)	6
i = 2	6	8	7

代码

/**
 * 二维数组的动态规划
 * 当前 dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
 * 第一行只能够向右走， 所以  dp[i][j] = grid[i][j] + dp[i][j - 1];
 * 第一列只能向下走，所以 dp[i][j] = grid[i][j] + dp[i - 1][j]
 */
var minPathSum = function(grid) {
    let rows = grid.length;
    let columns = grid[0].length;
    let dp = [];

    for(let i = 0; i < rows; i++) {
        let temp = [];
        for(let j = 0; j < columns; j++) {
            if(i == 0 && j == 0) {
                temp.push(grid[i][j]);
            } else if(j == 0) {
                temp.push(grid[i][j] + dp[i - 1][j]);
            } else if(i == 0) {
                temp.push(grid[i][j] + temp[j - 1])
            } else {
                temp.push(grid[i][j] + Math.min(dp[i - 1][j], temp[j - 1]))
            }

        }
        dp.push(temp);
    }
    return dp[rows - 1][columns - 1]
};