Minimum Path Sum Problem Solution

Minimum Path Sum Problem: 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.

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.

Minimum Path Sum Problem Solution

Problem Solution In Python

class Solution:
    def minPathSum(self, a: List[List[int]]) -> int:
        if len(a)==0:
            return 0
        m=len(a)
        n=len(a[0])
        c=[[0 for i in range(n)]for j in range(m)]
        c[0][0] = a[0][0]
        for i in range(1, n):
            c[0][i] = a[0][i]+c[0][i-1]
        for i in range(1, m):
            c[i][0] = a[i][0]+c[i-1][0]
        for i in range(1,m):
            for j in range(1,n):
                c[i][j] = min(c[i-1][j], c[i][j-1]) + a[i][j]
        return c[m-1][n-1]

Problem Solution In Java

import java.lang.Math;
class Solution {
    public int minPathSum(int[][] grid) 
    {
        int[][] dpStart = new int[grid.length + 1][grid[0].length + 1];
        return dummySoln(dpStart,grid,grid[0].length-1, grid.length-1);
    }
    public int dummySoln(int[][] dp,int[][] grid, int x, int y)
    {
        if(dp[y][x] != 0){return dp[y][x];}
        if(x == y && x == 0)
        {
            return grid[0][0];
        }
        int totalSum = grid[y][x];
        int totalSumLeft = -1;
        int totalSumUp = -1;
        if(x-1 >= 0)
        {
            totalSumLeft = totalSum + dummySoln(dp, grid, x - 1, y);
        }
        if(y-1 >= 0)
        {
            totalSumUp = totalSum + dummySoln(dp, grid, x, y-1);
        }
        if(totalSumLeft == -1 && totalSumUp != -1)
        {
            return totalSumUp;
        }
        if(totalSumLeft != -1 && totalSumUp == -1)
        {
            return totalSumLeft;
        }
        dp[y][x] = Math.min(totalSumLeft, totalSumUp);
        return Math.min(totalSumLeft, totalSumUp);
    }
}

Problem Solution In C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty())
            return 0;
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<long long int>> res(n, vector<long long int>(m, 0));
        
        res[0][0] = grid[0][0];
        
        for(size_t i = 1; i < n; i++){
            res[i][0] = res[i-1][0]+ grid[i][0];
        }
        for(size_t i = 1; i < m; i++){
            res[0][i] = res[0][i-1]+ grid[0][i];
        }
        
        for(size_t i = 1; i < n; i++){
            for(size_t j = 1; j < m; j++){
                res[i][j] = min(res[i-1][j] + grid[i][j], res[i][j-1] + grid[i][j]);
            }
        }
        
        return res[n-1][m-1];  
    }
};

Problem Solution In C

int min(int a,int b){
    if(a<b)
        return a;
    return b;
}

int minPathSum(int** grid, int gridSize, int* gridColSize){
    int m=gridSize,n=gridColSize[0];
    if(m==1 && n==1)
        return grid[0][0];
    
    if(m==1){
        int minn=0;
        for(int j=0;j<n;j++)
            minn+=grid[0][j];
         return minn;
    }
    else{
        int arr[m][n];
        arr[0][0]=grid[0][0];      
        for(int j=0;j<n;j++){
            for(int i=0;i<m;i++){
                if(i==0 && j==0)
                    continue;
                else if(i==0){
                    arr[i][j]=grid[i][j]+arr[i][j-1];
                }
                else if(j==0)
                    arr[i][0]=grid[i][0]+arr[i-1][j];
                else if(i>0 && i<m){
                    arr[i][j]=grid[i][j]+min(arr[i][j-1],arr[i-1][j]);
                }
            }
        }        
        return arr[m-1][n-1];
    }   
}