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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment