code-challenges/challenges/leetcode-3603-minimum-cost-path-with-alternating-directions-ii/py.py at master · rigwild/code-challenges · GitHub

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from typing import List, cast
import math

# import itertools
import functools


class Solution:
    def minCost(self, row: int, col: int, waitCost: List[List[int]]) -> int:
        INF = cast(int, math.inf)
        cache: List[List[int]] = [[INF] * col for _ in range(row)]
        # print(cache)

        def dp(i, j):
            if i < 0 or j < 0:
                return INF

            if i == 0 and j == 0:
                return 1

            if cache[i][j] != INF:
                return cache[i][j]

            cost = (
                min(
                    dp(i - 1, j),
                    dp(i, j - 1),
                )
                + (i + 1) * (j + 1)
                + waitCost[i][j]
            )

            cache[i][j] = cost
            return cost

        return dp(row - 1, col - 1) - waitCost[row - 1][col - 1]

    # -----------------------------------

    def minCost_tools(self, row: int, col: int, waitCost: List[List[int]]) -> int:
        INF = cast(int, math.inf)

        @functools.cache
        def dp(i, j):
            if i < 0 or j < 0:
                return INF

            if i == 0 and j == 0:
                return 1

            cost = (
                min(
                    dp(i - 1, j),
                    dp(i, j - 1),
                )
                + (i + 1) * (j + 1)
                + waitCost[i][j]
            )

            return cost

        return dp(row - 1, col - 1) - waitCost[row - 1][col - 1]