# 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.

Output Format

Return a single integer denoting the minimum sum of a path from cell (1, 1) to cell (M, N).

Example Input

``` A = [  [1, 3, 2]
[4, 3, 1]
[5, 6, 1]
]```

Example Output

` 9`

Example Explanation

``` The path is 1 -> 3 -> 2 -> 1 -> 1
So ( 1 + 3 + 2 + 1 + 1) = 8```

Constraints:

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m, n <= 200`
• `0 <= grid[i][j] <= 100`

Algorithm

We use an extra matrix dp of the same size as the original matrix. In this matrix dp(i,j) represents the minimum sum of the path from the index (i,j) to the bottom rightmost element. We start by initializing the bottom rightmost element of dp as the last element of the given matrix. Then for each element starting from the bottom right, we traverse backwards and fill in the matrix with the required minimum sums. Now, we need to note that at every element, we can move either rightwards or downwards. Therefore, for filling in the minimum sum, we use the equation:

``dp(i,j)= grid(i,j) + min(dp(i+1,j),dp(i,j+1));``
```class Solution {
public int minPathSum(int[][] grid) {

if(grid == null || grid.length == 0){
return 0;
}
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 < n ; i++){
dp[0][i] = grid[0][i] + dp[0][i-1];
}

for(int i = 1 ; i < m ; i++){
dp[i][0] = grid[i][0] + dp[i-1][0];
}

for(int i = 1 ; i < m ; i++){
for(int j = 1 ; j < n ; j++){
dp[i][j] = grid[i][j] + Math.min(dp[i][j-1], dp[i-1][j]);
}
}
return dp[m-1][n-1];
}
}
```

Complexity Analysis

• Time Complexity : O(mn). We traverse the entire matrix once.
• Space Complexity : O(mn). Another matrix of the same size is used.

Categories: Dynamic Programming