给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

示例1：
最小路径和 - 图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）
链接：https://leetcode.cn/problems/minimum-path-sum/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

自底向上的动态规划

二维数组

  1. function minPathSum(grid: number[][]): number {
  2.     const m = grid.length;
  3.     // 校验
  4.     if(m === 0) {
  5.         return 0;
  6.     } else if (m === 1 && grid[0].length === 1) { // 边界
  7.         return grid[0][0];
  8.     }
  9.     const n = grid[0].length;
  10.     const dp: Array<Array<number>> = new Array(m).fill(0).map(() => new Array(n).fill(0));
  11.     for (let i = 0; i < m; i++) {
  12.         for (let j = 0; j < n; j++) {
  13.             if (i === 0 && j === 0) {    // 左上角第一个特殊处理
  14.                 dp[0][0] = grid[0][0];
  15.             } else if (i === 0) {    // 第一列特殊处理
  16.                 dp[0][j] = dp[0][j-1] + grid[0][j];
  17.             } else if (j === 0) {    // 第一排特殊处理
  18.                 dp[i][0] = dp[i-1][0] + grid[i][0];
  19.             } else {
  20.                 dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; 
  21.             }
  22.         }
  23.     }
  24.     return dp[m - 1][n - 1];
  25. };

时间复杂度：O(mn)
空间复杂度：O(mn)

一维数组

function minPathSum(grid: number[][]): number {
    const m = grid.length;
    // 校验
    if(m === 0) {
        return 0;
    } else if (m === 1 && grid[0].length === 1) { // 边界
        return grid[0][0];
    }
    const n = grid[0].length;
    const dp: Array<number> = 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] = grid[0][0];
            } else if (i === 0) {    // 第一列特殊处理
                dp[j] = dp[j-1] + grid[0][j];
            } else if (j === 0) {    // 第一排特殊处理
                dp[j] = dp[j] + grid[i][0];
            } else {
                dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j]; 
            }
        }
    }
    return dp[n - 1];
};

时间复杂度：O(mn)
空间复杂度：O(n)