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

Explanation