In the 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.
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
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 100
Solution in C Programming
int minPathSum(int** grid, int gridSize, int* gridColSize){
for(int i=1; i<*gridColSize; i++)
grid[0][i] += grid[0][i-1];
for(int i=1; i<gridSize; i++)
grid[i][0] += grid[i-1][0];
for(int i=1; i<gridSize; i++)
for(int j=1; j<*gridColSize; j++)
grid[i][j] += grid[i][j-1] < grid[i-1][j] ? grid[i][j-1] : grid[i-1][j];
return grid[gridSize-1][*gridColSize-1];
}Solution in C++ Programming
class Solution {
public:
int f(vector<vector<int>> &grid, int m, int n){
vector<vector<int>> dp(m, vector<int>(n));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i==0 && j==0) dp[i][j] = grid[i][j];
else if(i==0 && j!=0) dp[i][j] = grid[i][j] + dp[i][j-1];
else if(i!=0 && j==0) dp[i][j] = grid[i][j] + dp[i-1][j];
else dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int ans = f(grid, m, n);
return ans;
}
};Solution in Java Programming
class Solution {
public int minPathSum(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
for(int i=1;i<m;i++) grid[i][0]+=grid[i-1][0];
for(int j=1;j<n;j++) grid[0][j]+=grid[0][j-1];
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
}
}
return grid[m-1][n-1];
}
}Solution in Python Programming
class Solution:
def minPathSum(self, grid):
H = len(grid)
L = len(grid[0])
out = [grid[0][0]]
for j in range(1,L):
out.append(grid[0][j]+out[-1])
for i in range(1,H):
for j in range(L):
if j == 0:
out[j] = grid[i][j]+out[j]
else:
out[j] = grid[i][j]+min(out[j],out[j-1])
return out[-1]
Solution in C# Programming
public class Solution
{
public int MinPathSum(int[][] grid)
{
int m = grid.Length;
int n = grid[0].Length;
int[,] dp = new int[m,n];
dp[0,0] = grid[0][0];
for(int i=1; i < m; ++i)
dp[i,0] = dp[i-1, 0] + grid[i][0];
for(int j=1; j < n; ++j)
dp[0,j] = dp[0,j-1] + grid[0][j];
for(int i=1; i <m ; ++i)
{
for(int j=1; j <n ; ++j)
{
dp[i,j] = Math.Min(dp[i-1, j],dp[i, j -1]) + grid[i][j];
}
}
return dp[m-1,n-1];
}
}Also read,