leetcode64：最小路径和

[sisterAn]

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

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

 

示例 1：

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

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

leetcode

[sisterAn]

1、DP方程
当前项最小路径和 = 当前项值 + 上项或左项中的最小值
grid[i][j] += Math.min( grid[i - 1][j], grid[i][j - 1] )

2、边界处理
grid的第一行与第一列 分别没有上项与左项 故单独处理计算起项最小路径和
计算第一行：

for(let j = 1; j < col; j++) grid[0][j] += grid[0][j - 1]

计算第一列：

for(let i = 1; i < row; i++) grid[i][0] += grid[i - 1][0]

3、代码实现

var minPathSum = function(grid) {
    let row = grid.length, col = grid[0].length

    // calc boundary
    for(let i = 1; i < row; i++)
        // calc first col
        grid[i][0] += grid[i - 1][0]

    for(let j = 1; j < col; j++)
        // calc first row
        grid[0][j] += grid[0][j - 1]

    for(let i = 1; i < row; i++)
        for(let j = 1; j < col; j++)
            grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])
    
    return grid[row - 1][col - 1]
};

[cutie6]

这里计算的方向是从右下角到左上角吧

[fengmiaosen]

/**
 * 
 * @param {number[][]} grid 
 */
function minPathSum(grid) {
    if (grid.length < 1 || grid[0].length < 1) {
        return 0
    }

    let m = grid.length
    let n = grid[0].length

    let dp = new Array(m).fill(undefined).map(() => {
        return new Array(n).fill(0)
    })

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // 左上角
            if (i === 0 && j === 0) {
                dp[0][0] = grid[0][0]
            } else if (i == 0 && j !== 0) {
                // 第一行
                dp[i][j] = dp[i][j - 1] + grid[i][j]
            } else if (i != 0 && j == 0) {
                // 第一列
                dp[i][j] = dp[i - 1][j] + grid[i][j]
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
            }
        }
    }

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

[TonyZhang1993]

看了labuladong 写的 click here

var minPathSum = function(grid) {
  let m = grid.length
  let n = grid[0].length
  //  备忘录
  let memo = Array.from({length: m}, ()=> Array(n).fill(9999))

  //  dp的定义 - 当前坐标最小的路径和
  const dp = (matrix, i, j, memo) => {
    //  处理合法性
    if (i<0 || j<0) {
      return 10000
    }
    //  base case 
    if(i ===0 && j === 0) {
      return matrix[0][0]
    }
    //  备忘录
    if (memo[i][j] !== 9999) {
      return memo[i][j]
    }
    //  当前dp值 = 该点的坐标值 + 左方 和 上方的dp 值
    memo[i][j] = matrix[i][j]+ Math.min(dp(matrix, i-1, j, memo), dp(matrix, i, j-1, memo))

    return memo[i][j]
  }
  //  将终点坐标带入
  return dp(grid, m-1, n-1, memo)

};