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

 

给定一个包含非负整数的 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] <= 200

本题使用动态规划，将问题拆分成小问题，寻找小问题之间的递推规律。

通过代码：

//本题使用动态规划，递推式为：a[i][j]=min(a[i][j]+a[i-1]a[j], a[i][j]+a[i][j-1])
class Solution {
public:
    long long res[202][202];
    int minPathSum(vector<vector<int>>& grid) {
        long long add_upper = 0, add_left = 0;
        res[0][0] = grid[0][0];
        for (int i=0;i<grid.size();i++) {
            for (int j=0;j<grid[i].size();j++) {
                if (i==0&&j==0) {
                    continue;
                }
                add_upper = grid[i][j];
                add_left = grid[i][j];
                if (i-1>=0) {
                    add_upper += res[i-1][j];
                } else {
                    add_upper = INT_MAX;
                }
                if (j-1>=0) {
                    add_left += res[i][j-1];
                } else {
                    add_left = INT_MAX;
                }
                res[i][j] = min(add_upper, add_left);
            }
        }
        int n = grid.size();
        int m = grid[0].size();
        return res[n-1][m-1];
    }
};