Leetcode - Minimum Path Sum

题目链接

Minimum Path Sum

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.

解题思路

TODO （稍后补充）

解答代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty()) return 0;
        int sum=0;
        
        vector<vector<int> > minMatrix(grid.size(), vector<int>(grid[0].size(), 0));
        
        int zeroSum = 0;
        for(int i=0;i<grid[0].size();i++) {
            zeroSum += grid[0][i];
            minMatrix[0][i] = zeroSum;
        }
        
        zeroSum = 0;
        for(int i=0;i<grid.size();i++) {
            zeroSum += grid[i][0];
            minMatrix[i][0] = zeroSum;
        }
        
        for(int i=1;i<grid.size();i++) {
            for(int j=1;j<grid[i].size();j++) {
                minMatrix[i][j] = minMatrix[i-1][j] >= minMatrix[i][j-1] ? minMatrix[i][j-1]+grid[i][j] : minMatrix[i-1][j]+grid[i][j];
            }
        }
        
        return minMatrix[grid.size()-1][grid[0].size()-1];
    }
};