数据结构与算法之LeetCode-64-最小路径和（动态规划求解）

64. 最小路径和 - 力扣（LeetCode）

• 假设dp为 m*n的矩阵，其中dp[i][j]的值代表直走到(i,j)的最小路径和
• 状态转移方程（走到单元格（i，j）的最小路径和 = “从左侧（i-1，j）和上方）（i，j-1）移动到下一个位置，因此只需要考虑上边界和左边界，以及两个最小路径和中的较小值“+当前单元格的grid[i][j]）
  • 左边和上边都不是边界：也就是i!=0,j!=0时，dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]
  • 只有左边是矩阵边界：只能从上面移动到下面,也就是i=0,j!=0,dp[i][j] = dp[i][j-1]+grid[i][j]
  • 只有上面是矩形边界：只能从左边移动，也就是i!=0,j=0, dp[i][j]=dp[i-1][j]+grid[i][j]
    • 上边和左边都是矩阵边界，i=0,j=0,就是起点dp[i][j]=grid[i][j]

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  let m = grid.length,
    n = grid[0].length;
  let dp = new Array(m).fill(0).map(() => 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[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1])+grid[i][j];
        }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 if(i==0&&j==0){
            dp[i][j] = grid[0][0]
        }
    }
  }
  return dp[m - 1][n - 1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

执行结果：通过

执行用时：68 ms, 在所有 JavaScript 提交中击败了57.45%的用户

内存消耗：44.2 MB, 在所有 JavaScript 提交中击败了14.67%的用户

通过测试用例：61 / 61

参考链接

64. 最小路径和 - 力扣（LeetCode）

最小路径和 （动态规划，规范流程，清晰图解） - 最小路径和 - 力扣（LeetCode）
最小路径和 - 最小路径和 - 力扣（LeetCode）