题目描述

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

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

样例

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

算法

(动态规划) $O(n^2)$

第一行只能往右走，所有值累加。
第一列只能往下走，所有值累加。
其他位置只能从左边或上边过来，取最小值:
$f(i, j)=\min \{f(i, j-1), f(i-1, j)+grid[i][j] \}$
即，
$f(i, j) =\min \{f(i, j-1), f(i-1, j) \} + grid[i][j]$

时间复杂度

时间复杂度$O(n^2)$,空间复杂度$O(n)$，可以用滚动数组优化为一维空间$O(n)$

C++ 代码

二维DP

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty() || grid[0].empty()) return 0;  // 特判：行为空或列为空
        int m = grid.size(), n = grid[0].size();  // m*n的矩阵
        vector<vector<int>> f(m, vector<int>(n));  // 定义f[m][n]
        f[0][0] = grid[0][0];
        for(int i = 1; i < n; i++) f[0][i] = f[0][i - 1] + grid[0][i];  // 第一行(0,j)累加
        for(int i = 1; i < m; i++) f[i][0] = f[i - 1][0] + grid[i][0];  // 第一列(i,0)累加
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];  // 其他位置(i,j)从左边或右边过来
        return f[m - 1][n - 1];
    }
};

一维DP

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty() || grid[0].empty()) return 0;  // 特判：行为空或列为空
        int m = grid.size(), n = grid[0].size();  // m*n的矩阵
        vector<int> f(n);  // 定义f[n]
        f[0] = grid[0][0];
        for(int i = 1; i < n; i++) f[i] = f[i - 1] + grid[0][i]; 

        for(int i = 1; i < m; i++)
        {
            f[0] += grid[i][0];
            for(int j = 1; j < n; j++)
                f[j] = min(f[j], f[j - 1]) + grid[i][j];  // 其他位置(i,j)从左边或右边过来
        }
        return f[n - 1];
    }
};