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];

    }

};