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
# Video: https://www.youtube.com/watch?v=lBRtnuxg-gU
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
T = [[0] * n for _ in range(m)]
# First left top corner cost is same.
T[0][0] = grid[0][0]
# First row in T
for first_row_idx in range(1, n):
T[0][first_row_idx] = T[0][first_row_idx-1] + grid[0][first_row_idx]
# First col in T
for first_col_idx in range(1, m):
T[first_col_idx][0] = T[first_col_idx-1][0] + grid[first_col_idx][0]
# 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)))