64. Minimum Path Sum | LeetCode Solution

 64. Minimum Path Sum | LeetCode Solution

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] <= 100
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid[0].size();
        vector<int>prev(m,0);
        
        
        for(int i=0; i<grid.size(); i++){
            vector<int>curr(m,0);
            for(int j=0; j<grid[0].size(); j++){
                if(i==0 && j==0){
                    curr[j]=grid[i][j];
                }
                else{
                    int up=grid[i][j];
                    if(i>0)up+=prev[j];
                    else up+=1e9;
                    
                    int left=grid[i][j];
                    if(j>0)left+=curr[j-1];
                    else left+=1e9;
                    
                    curr[j]=min(left,up);
                    
                }
                
            }
            prev=curr;
        }
        return prev[grid[0].size()-1];
    }
};

Post a Comment

0 Comments