## Algorithm

Problem Name: 64. Minimum Path Sum

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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>

int minPathSum(int **grid, int nRows, int nCols) {
int i, j;
for (i = 0; i  <  nRows; i++) {
for (j = 0; j  <  nCols; j++) {
if (i > 0 && j == 0)
grid[i][j] += grid[i - 1][j];
if (j > 0 && i == 0)
grid[i][j] += grid[i][j - 1];
if (i > 0 && j > 0) {
if (grid[i][j - 1]  <  grid[i - 1][j])
grid[i][j] += grid[i][j - 1];
else
grid[i][j] += grid[i - 1][j];
}
}
}
/*
for (i = 0; i  <  nRows; i++) {
for (j = 0; j  <  nCols; j++) {
printf("%d ", grid[i][j]);
}
printf("\n");
}
*/
return grid[nRows - 1][nCols - 1];
}

int main() {
int m, n, i;
m = n = 3;
int **grid = (int **) calloc (m, sizeof(int *));

for (i = 0; i  <  m; i++)
grid[i] = (int *) calloc (n, sizeof(int));

grid[0][0] = 1; grid[0][1] = 2; grid[0][2] = 3;
grid[1][0] = 1; grid[1][1] = 2; grid[1][2] = 3;
grid[2][0] = 1; grid[2][1] = 2; grid[2][2] = 3;

printf("%d\n", minPathSum(grid, m, n));
return 0;
}
``````
Copy The Code &

Input

cmd
grid = [[1,3,1],[1,5,1],[4,2,1]]

Output

cmd
7

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.empty()) return 0;
int m = grid.size(), n = grid[0].size();
vector<vector < int>>dp(m, vector<int>(n));
dp[0][0] = grid[0][0];
for(int i = 1; i  <  m; i++) dp[i][0] = grid[i][0] + dp[i - 1][0];
for(int i = 1; i  <  n; i++) dp[0][i] = grid[0][i] + dp[0][i - 1];
for(int i = 1; i  <  m; i++)
for(int j = 1; j  <  n; j++)
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]> + grid[i][j];
return dp[m - 1][n - 1];
}
};
``````
Copy The Code &

Input

cmd
grid = [[1,2,3],[4,5,6]]

Output

cmd
12

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
for (int i = 0; i  <  dp.length; i++) {
for (int j = 0; j  <  dp[i].length; j++) {
dp[i][j] += grid[i][j];
if (i > 0 && j > 0) {
dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1]);
} else if (i > 0) {
dp[i][j] += dp[i - 1][j];
} else if (j > 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
return dp[grid.length - 1][grid[0].length - 1];
}
}
``````
Copy The Code &

Input

cmd
grid = [[1,3,1],[1,5,1],[4,2,1]]

Output

cmd
7

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const minPathSum = function(grid) {
const m = grid.length;
const n = grid[0].length;
for (let i = 1; i  <  n; i++) {
grid[0][i] += grid[0][i - 1];
}
for (let i = 1; i  <  m; i++) {
grid[i][0] += grid[i - 1][0];
}
for (let i = 1; i  <  m; i++) {
for (let j = 1; j  <  n; j++) {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[m - 1][n - 1];
};
``````
Copy The Code &

Input

cmd
grid = [[1,3,1],[1,5,1],[4,2,1]]

Output

cmd
7

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
for i in range(len(grid)):
for j in range(len(grid[0])):
grid[i][j] += min(grid[i][j - 1] if j > 0 else float("inf"), grid[i - 1][j] if i > 0 else float("inf")) if i!=0 or j != 0 else 0
return grid[-1][-1]
``````
Copy The Code &

Input

cmd
grid = [[1,2,3],[4,5,6]]

Output

cmd
12

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _064_MinimumPathSum
{
public int MinPathSum(int[][] grid)
{
var rowLenght = grid.Length;
var columnLenght = grid[0].Length;

var pathSum = new int[columnLenght];
for (int i = 0; i  <  columnLenght; i++)
pathSum[i] = int.MaxValue;
pathSum[0] = 0;

for (int i = 0; i  <  rowLenght; i++)
{
pathSum[0] += grid[i][0];
for (int j = 1; j  <  columnLenght; j++)
pathSum[j] = Math.Min(pathSum[j - 1], pathSum[j]) + grid[i][j];
}

return pathSum[columnLenght - 1];
}
}
}
``````
Copy The Code &

Input

cmd
grid = [[1,2,3],[4,5,6]]

Output

cmd
12