# Min Cost Path¶

## Question¶

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.

Problem Source: https://leetcode.com/problems/minimum-path-sum/

## Solution¶

```# min_cost_path.py - 26-04-2020 09:11

from typing import List

class Solution:

def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid)
T = [ * n for _ in range(m)]
# First left top corner cost is same.
T = grid

# First row in T
for first_row_idx in range(1, n):
T[first_row_idx] = T[first_row_idx-1] + grid[first_row_idx]

# First col in T
for first_col_idx in range(1, m):
T[first_col_idx] = T[first_col_idx-1] + grid[first_col_idx]

# Fill in the rest of the 2D matrix for T.
for i in range(1, m):
for j in range(1, n):
T[i][j] = grid[i][j] + min(T[i-1][j],   # top
T[i][j-1])   # left

# value to reach the right most end
return T[-1][-1]

if __name__ == '__main__':
s = Solution()
mat = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
print((s.minPathSum(mat)))
```