# Leetcode Minimum Path Sum problem solution

Apr 15, 2023

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

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.