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.
Table of Contents
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];
}
}