Minimum Path Cost in a Grid LeetCode solution in Python

1
class Solution:
2
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
3
        max_row, max_col = len(grid), len(grid[0])
4
        dp = [[-1] * max_col for _ in range(max_row)]
5

6
        def recursion(row, col):
7
            if row == max_row - 1:  # If last row then return nodes value
8
                return grid[row][col]
9
            if (
10
                dp[row][col] == -1
11
            ):  # If DP for this node is not computed then we will do so now.
12
                current = grid[row][col]  # Current Node Value
13
                res = float("inf")  # To store best path from Current Node
14
                for c in range(max_col):  # Traverse all path from Current Node
15
                    val = moveCost[current][c] + recursion(
16
                        row + 1, c
17
                    )  # Move cost + Target Node Value
18
                    res = min(res, val)
19
                dp[row][col] = (
20
                    res + current
21
                )  # DP[current node] = Best Path + Target Node Val + Current Node Val
22
            return dp[row][col]
23

24
        for c in range(max_col):
25
            recursion(0, c)  # Start recursion from all nodes in 1st row
26
        return min(dp[0])  # Return min value from 1st row