## Description

https://leetcode.com/problems/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:**

Input:[ [1,3,1], [1,5,1], [4,2,1] ]Output:7Explanation:Because the path 1→3→1→1→1 minimizes the sum.

## Explanation

dp(i,j)=grid(i,j)+min(dp(i+1,j),dp(i,j+1))

## Python Solution

```
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
min_paths = [[0 for j in range(0, len(grid[0]))] for i in range(0, len(grid))]
min_paths[0][0] = grid[0][0]
for j in range(1, len(grid[0])):
min_paths[0][j] = min_paths[0][j - 1] + grid[0][j]
for i in range(1, len(grid)):
min_paths[i][0] = min_paths[i - 1][0] + grid[i][0]
for i in range(1, len(grid)):
for j in range(1, len(grid[0])):
min_paths[i][j] = min(min_paths[i][j - 1], min_paths[i - 1][j]) + grid[i][j]
return min_paths[len(grid) - 1][len(grid[0]) - 1]
```

- Time complexity: O(MN). We traverse the entire matrix once.
- Space complexity: O(MN). Another matrix of the same size is used.

## One Thought to “LeetCode 64. Minimum Path Sum”