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.

&nbsp;
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


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 200
	0 &lt;= grid[i][j] &lt;= 100


class Solution:

    def minPathSum(self, grid: List[List[int]]) -> int:
        prev=[0]*len(grid[0])
        for i in range(len(grid)):
            temp=[0]*len(grid[0])
            for j in range(len(grid[0])):
                if i==0 and j==0:
                    temp[j]=grid[i][j]
                    continue
                if i>0:
                    lft=grid[i][j]+prev[j]
                else:
                    lft=grid[i][j]+1000
                if j>0:
                    up=grid[i][j]+temp[j-1]
                else:
                    up=grid[i][j]+1000
                temp[j]=min(up,lft)
            prev=temp
        return prev[-1]
    
        
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0];

        for(int i=1;i<n;i++){
            dp[i] = dp[i-1]+grid[0][i];
        }

        for(int i=1;i<m;i++){
             for(int j=0;j<n;j++){
                 if(j == 0)
                     dp[j] += grid[i][j];
                 else
                     dp[j] = Math.min(dp[j],dp[j-1])+grid[i][j];
            }
        }

        return dp[n-1];
    }
}
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        vector<vector<int>> dp(n,vector<int>(m,0));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(i==0 && j==0)
                    dp[i][j]=grid[i][j];
                else if(i==0)
                    dp[i][j]=dp[i][j-1]+grid[i][j];
                else if(j==0)
                    dp[i][j]=dp[i-1][j]+grid[i][j];
                else
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[n-1][m-1];
    }
};
var minPathSum = function(grid) {
    let row = grid.length;
    let col = grid[0].length;

    for(let i = 1; i < row; i++) {
        grid[i][0] += grid[i-1][0];
    }
    for(let j = 1; j < col; j++) {
        grid[0][j] += grid[0][j-1];
    }
    for(let i = 1; i < row; i++) {
        for(let j = 1; j < col; j++) {
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }
    return grid[row-1][col-1];
};
Minimum Path Sum