Leetcode Minimum Path Sum Problem Solution

In this Leetcode Minimum Path Sum Problem 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.

Problem solution in Python.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0:
                    if j == 0:
                        dp[i][j] = grid[i][j]
                    else:
                        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] + grid[i][j], dp[i][j-1] + grid[i][j])
 
        return dp[-1][-1]

Problem solution in Java.

class Solution {
   
    
    public int minPathSum(int[][] grid) {
        if(grid==null||grid.length==0)
            return 0;
        int[][] memo = new int[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            Arrays.fill(memo[i],Integer.MAX_VALUE);
        }
        return func(grid.length-1,grid[0].length-1,grid,memo);
    }
    
    public int func(int row, int column, int[][] grid, int[][] memo){
        if(row<0||column<0)
            return Integer.MAX_VALUE;
        else if(memo[row][column]!=Integer.MAX_VALUE)
            return memo[row][column];
        else if(row==0 && column==0)
            return grid[0][0];
        else {
            memo[row][column]= grid[row][column] + Math.min(func(row-1,column,grid,memo),func(row,column-1,grid, memo)); 
            return memo[row][column];
        }
 
 
       }
 
}

Problem solution in C++.

typedef pair<int,pair<int,int>> pii;
class comp
{
    public:
    bool operator()(pii a,pii b)
    {
        return a.first>b.first;
    }
};
 
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        priority_queue<pii,vector<pii>,comp> pq;
        pq.push({grid[0][0],{0,0}});
        grid[0][0]=-1;
        while(!pq.empty())
        {
            int cur=pq.top().first;
            int x=pq.top().second.first;
            int y=pq.top().second.second;
 
            int len=pq.size();
            //cout<<x<<" "<<y<<" "<<cur<<" "<<pq.size()<<endl;
            if(x==grid.size()-1 && y==grid[0].size()-1)
            {
                return cur;
            }
            pq.pop();
 
            while(len>0)
            {
                len--;
                int a=x+1;
                int b=y;
                if(a<grid.size() && grid[a][b]!=-1)
                {
                    pq.push({cur+grid[a][b],{a,b}});
                    grid[a][b]=-1;
                }
 
                int c=x;
                int d=y+1;
 
                if(d<grid[0].size() && grid[c][d]!=-1)
                {
                    pq.push({cur+grid[c][d],{c,d}});
                    grid[c][d]=-1;
                }
 
            }
        }
 
        return -1;
    }
};

Problem solution in C.

int minPathSum(int **grid, int nRows, int nCols) {
    int*pc, *pu, *pl, *pe, **ppc, **ppu, **ppe;
    for(ppu = grid, ppc = ppu + 1, ppe = ppu + nRows; ppc < ppe; ppu = ppc, ++ppc){
        **ppc += **ppu;
    }
    for(pl = grid[0], pc = pl + 1, pe = pl + nCols; pc < pe; pl = pc, ++pc){
        *pc += *pl;
    }
    for(ppu = grid, ppc = ppu + 1, ppe = ppu + nRows; ppc < ppe; ppu = ppc, ++ppc){
        for(pl = ppc[0], pu = ppu[0] + 1, pc = pl + 1, pe = pl + nCols; pc < pe; pl = pc, ++pc, ++pu){
            *pc += (*pl <= *pu ? *pl : *pu);
        }
    }
    return grid[nRows-1][nCols-1];
}