1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38# Youtube Explanation: https://www.youtube.com/watch?v=lBRtnuxg-gU
from __future__ import annotations
def minimum_cost_path(matrix: list[list[int]]) -> int:
"""
Find the minimum cost traced by all possible paths from top left to bottom right in
a given matrix
>>> minimum_cost_path([[2, 1], [3, 1], [4, 2]])
6
>>> minimum_cost_path([[2, 1, 4], [2, 1, 3], [3, 2, 1]])
7
"""
# preprocessing the first row
for i in range(1, len(matrix[0])):
matrix[0][i] += matrix[0][i - 1]
# preprocessing the first column
for i in range(1, len(matrix)):
matrix[i][0] += matrix[i - 1][0]
# updating the path cost for current position
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
matrix[i][j] += min(matrix[i - 1][j], matrix[i][j - 1])
return matrix[-1][-1]
if __name__ == "__main__":
import doctest
doctest.testmod()