Note: You can only move either down or right at any point in time.
Solution: compute the minimum path sum for each element grid (i, j) from top left row by row.
class Solution { public: int minPathSum(vector<vector<int> > &grid) { // Start typing your C/C++ solution below // DO NOT write int main() function if(grid.empty() || grid[0].empty()) return 0; int x = grid.size(), y=grid[0].size(); for(int i=0; i<x; i++) for(int j=0; j<y; j++){ if(i==0) grid[i][j] += (j==0?0:grid[i][j-1]); else grid[i][j] += min(grid[i-1][j], (j==0?INT_MAX:grid[i][j-1])); } return grid.back().back(); } };
No comments:
Post a Comment