64. Minimum Path Sum --- M

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

 

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

A:
就是简单的DP 问题。 从top-left开始，计算，到bottom-right 截止

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> V(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    V[0][0] = grid[0][0];
                    continue;
                }
                auto left = j - 1 >= 0 ? V[i][j - 1] : INT_MAX;
                auto up = i - 1 >= 0 ? V[i - 1][j] : INT_MAX;
                V[i][j] = grid[i][j] + min(left, up);
            }
        }
        return V[m - 1][n - 1];
    }
};

Mistakes:
1: 计算最下面一行和最右边一列的时候，不是简单的copy而应该是到右下角点的sum的值。


---------------------------第二遍----------直接在数组上修改-----------------
思路：刚开始扫描第一行和第一列
然后，每次再扫描并计算 剩下的grid的第一行和第一列。 分别update 节点的值。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                if(i==0 && j == 0){
                    continue;
                }
                int left = j -1 >=0 ? grid[i][j-1]: INT_MAX;
                int up = i -1 >=0 ? grid[i-1][j] : INT_MAX;
                grid[i][j] += min(left, up);
            }
        }
        return grid[m-1][n-1];
    }
};