64. 最小路径和

[wengzc]

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

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

示例:

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

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

[wengzc]

思路分析：动态规划

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
    let len = grid.length
    // dp[i][j]含义指到达i、j位置路径上的最小数字总和
    let dp = new Array(len)
    for (let i = 0; i < len; i++) {
        dp[i] = new Array(grid[0].length)
    }
    let sum1 = 0
    for (let i = 0; i < grid[0].length; i++) {
        sum1 += grid[0][i]
        // base case
        dp[0][i] = sum1
    }
    let sum2 = 0
    for (let i = 0; i < len; i++) {
        sum2 += grid[i][0]
        // base case
        dp[i][0] = sum2
    }
    for (let i = 1; i < len; i++) {
        for (let j = 1; j < grid[0].length; j++) {
            // 状态转移方程
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        }
    }
    return dp[len - 1][grid[0].length - 1]
};