forked from TheAlgorithms/Python
- Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathminimum_cost_path.py
37 lines (25 loc) · 936 Bytes
/
minimum_cost_path.py
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
# Youtube Explanation: https://www.youtube.com/watch?v=lBRtnuxg-gU
from __future__ importannotations
defminimum_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
foriinrange(1, len(matrix[0])):
matrix[0][i] +=matrix[0][i-1]
# preprocessing the first column
foriinrange(1, len(matrix)):
matrix[i][0] +=matrix[i-1][0]
# updating the path cost for current position
foriinrange(1, len(matrix)):
forjinrange(1, len(matrix[0])):
matrix[i][j] +=min(matrix[i-1][j], matrix[i][j-1])
returnmatrix[-1][-1]
if__name__=="__main__":
importdoctest
doctest.testmod()
