# LeetCode 64. Minimum Path Sum

## 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: 7
Explanation: 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))] for i in range(0, len(grid))]

min_paths = grid
for j in range(1, len(grid)):
min_paths[j] = min_paths[j - 1] + grid[j]

for i in range(1, len(grid)):
min_paths[i] = min_paths[i - 1] + grid[i]

for i in range(1, len(grid)):
for j in range(1, len(grid)):
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) - 1]
``````
• Time complexity: O(MN). We traverse the entire matrix once.
• Space complexity: O(MN). Another matrix of the same size is used.