FilesExpand file tree

 master

/

minimum_cost_path.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

37 lines (25 loc) · 936 Bytes

 master

/

minimum_cost_path.py

Copy path

Top

File metadata and controls

• Code
• Blame

37 lines (25 loc) · 936 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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__ 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()