Leetcode 64. 最小路径和【C++】

地址：https://leetcode-cn.com/problems/minimum-path-sum/

题目

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

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

示例:

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

解题思路

动态规划问题。

1. 状态：从左上角到 grid[i][j] 的最小路径和；
2. 转移方程：F[i][j] = grid[i][j] + min(F[i - 1][j], F[i][j - 1]) 。

源码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int r = grid.size();  // 行
        int c = grid[0].size();  // 列
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(i == 0 && j == 0) continue;
                int m = 2147483647;  //最大正整数
                if(i > 0) m = min(m, grid[i - 1][j]);
                if(j > 0) m = min(m, grid[i][j - 1]);
                grid[i][j] += m;  //把每一个格子的值修改为从左上角到该格子的最小路径和
            }
        }
        return grid[r - 1][c - 1];
    }
};