youtube explanation https www youtube comwatch vlbrtnuxggu find the minimum cost traced by all possible paths from top left to bottom right in a given matrix minimumcostpath2 1 3 1 4 2 6 minimumcostpath2 1 4 2 1 3 3 2 1 7 preprocessing the first row preprocessing the first column updating the path cost for current position youtube explanation https www youtube com watch v lbrtnuxg gu 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 preprocessing the first column updating the path cost for current position
from __future__ import annotations


def minimum_cost_path(matrix: list[list[int]]) -> int:
    

    
    for i in range(1, len(matrix[0])):
        matrix[0][i] += matrix[0][i - 1]

    
    for i in range(1, len(matrix)):
        matrix[i][0] += matrix[i - 1][0]

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