  # LeetCode - Minimum Path Sum

## Problem statement

Given a m x n grid filled with non-negative numbers, find a path from the top left to the 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 statement taken from: https://leetcode.com/problems/minimum-path-sum

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
``````

### Explanation

#### Brute force approach

The brute force approach is to generate all possible paths from top left to bottom right. We calculate the sum of all these paths and find the minimum. The solution works for small-sized arrays but will timeout for big-sized arrays.

#### Optimal Substructure

The path to reach (m, n) must be through one of the two cells: (m - 1, n) or (m, n - 1). The minimum cost to reach (m, n) can be calculated as 'minimum of the two cells plus grid(m, n)'.

``minimumCost(m, n) = min(minimumCost(m - 1, n), minimumCost(m, n - 1)) + grid(m, n)``
``````int minCost(int grid[R][C], int m, int n)
{
if (n < 0 || m < 0)
return INT_MAX;
else if (m == 0 && n == 0)
return grid[m][n];
else
return grid[m][n] +
min(
minCost(grid, m - 1, n),
minCost(grid, m, n - 1)
);
}``````

#### Dynamic Programming

The above optimal substructure is solved using a recursive approach. But, if we note closely, the above approach computes the same sub-problems again and again.

We can avoid recomputing the same sub-problems using dynamic programming approach. We create a 2D array and solve the problem in a bottom-up manner.

``````- set m = grid.size()
n = grid.size()
dp(m, vector<int>(n))

- loop for i = 0; i < m; i++
loop for j = 0; j <n; j++

if i == 0 && j == 0
- set dp[i][j] = grid[i][j]
else if i == 0
- set dp[i][j] = dp[i][j - 1] + grid[i][j]
else if j == 0
- set dp[i][j] = dp[i - 1][j] + grid[i][j]
else
- set dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
- for end

- return dp[m - 1][n - 1]
``````

The time complexity of this approach is O(N^2), and the space complexity is O(M*N).

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid.size();
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) {
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], dp[i][j - 1]) + grid[i][j];
}
}
}

return dp[m - 1][n - 1];
}
};``````

#### Golang solution

``````func minPathSum(grid [][]int) int {
m := len(grid)
n := len(grid)
dp := make([][]int, m)

for k := range dp {
dp[k] = make([]int, n)
}

for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 && j == 0 {
dp[i][j] = grid[i][j]
} else if i == 0 {
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][j - 1], dp[i - 1][j]) + grid[i][j]
}
}
}

return dp[m - 1][n - 1]
}

func min(a, b int) int {
if a < b {
return a
}
return b
}``````

#### Javascript solution

``````var minPathSum = function(grid) {
let m = grid.length;
let n = grid.length;
let dp = new Array(m);

for(let k = 0; k < dp.length; k++) {
dp[k] = new Array(n);
}

for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(i == 0 && j == 0) {
dp[i][j] = grid[i][j];
} else if(i == 0) {
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] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
}

return dp[m - 1][n - 1];
};``````

#### Dry Run

Let's dry-run our algorithm for Example 2.

``````Input: grid = [[1, 2, 3], [4, 5, 6]]

Step 1: m = grid.size()
= 2
n = grid.size()
= 3

dp(2, 3)

Step 2: loop for i = 0; i < m
0 < 2
true

loop for j = 0; j < n
0 < 3
true

if i == 0 && j == 0
true

dp[i][j] = grid[i][j]
= grid
= 1

dp = [[1, 0, 0], [0, 0, 0]]

j++

j = 1
j < n
1 < 3
true

if i == 0 && j == 0
true
else if i == 0
true

dp[i][j] = dp[i][j - 1] + grid[i][j]
= dp[1 - 1] + grid
= dp + grid
= 1 + 2
= 3

dp = [[1, 3, 0], [0, 0, 0]]

j++
j < n
2 < 3
true

if i == 0 && j == 0
true
else if i == 0
true

dp[i][j] = dp[i][j - 1] + grid[i][j]
= dp[2 - 1] + grid
= dp + grid
= 3 + 3
= 6

dp = [[1, 3, 6], [0, 0, 0]]

j++
j < n
3 < 3
false

i++
i = 1

Step 3: loop for i < m
1 < 2
true

loop for j = 0; j < n
0 < 3
true

if i == 0 && j == 0
false
else if i == 0
false
else if j == 0
true

dp[i][j] = dp[i - 1][j] + grid[i][j]
= dp[1 - 1] + grid
= dp + grid
= 1 + 4
= 5

dp = [[1, 3, 6], [5, 0, 0]]

j++
j < n
1 < 3
true

if i == 0 && j == 0
false
else if i == 0
false
else if j == 0
false
else

dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
= min(dp[1 - 1], dp[1 - 1]) + grid
= min(dp, dp) + 5
= min(5, 3) + 5
= 3 + 5
= 8

dp = [[1, 3, 6], [5, 8, 0]]

j++
j < n
2 < 3
true

if i == 0 && j == 0
false
else if i == 0
false
else if j == 0
false
else

dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
= min(dp[2 - 1], dp[1 - 1]) + grid
= min(dp, dp) + 6
= min(8, 6) + 6
= 6 + 6
= 12

dp = [[1, 3, 6], [5, 8, 12]]

j++
j < n
3 < 3
false

i++
i = 2

Step 4: loop for i < m
2 < 2
false

Step 5: return dp[m - 1][n - 1]
dp[2 - 1][3 - 1]
dp
12

We return the answer as 12.
``````