Number of Paths with Max Score LeetCode solution in Python

1
# Runtime: 321 ms (Top 53.09%) | Memory: 26.5 MB (Top 8.64%)
2
class Solution:
3
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
4

5
        ## Basic information: height and width of board
6
        h, w = len(board), len(board[0])
7

8
        # ----------------------------------------------------------------------------
9

10
        # Use pathon native cahce as memoization for DP
11
        @cache
12
        def visit(i, j):
13

14
            if i == h - 1 and j == w - 1:
15
                ## Base case:
16

17
                # score for start coordinate = 0
18
                # paht count for start coordinate = 1
19
                return 0, 1
20

21
            elif i >= w or j >= h or board[i][j] == "X":
22

23
                ## Base case:
24
                # Out-of-boundary, or meet obstacle
25
                return 0, 0
26

27
            ## General case:
28
            # update from three possible preivous moves from right, down, and diagonal
29

30
            right_score, right_path_count = visit(i, j + 1)
31
            down_score, down_path_count = visit(i + 1, j)
32
            diag_score, diag_path_count = visit(i + 1, j + 1)
33

34
            max_prevScore = max(right_score, down_score, diag_score)
35

36
            cur_path_count = 0
37
            cur_score = int(board[i][j]) if board[i][j] != "E" else 0
38

39
            if right_score == max_prevScore:
40
                cur_path_count += right_path_count
41
            if down_score == max_prevScore:
42
                cur_path_count += down_path_count
43
            if diag_score == max_prevScore:
44
                cur_path_count += diag_path_count
45

46
            return max_prevScore + cur_score, cur_path_count
47

48
        # ----------------------------------------------------------------------------
49

50
        ## Remark: Remember to take modulo by constant, this is defined by description
51
        CONST = 10**9 + 7
52
        maxScore, validPathCount = visit(0, 0)
53

54
        return [maxScore % CONST, validPathCount % CONST] if validPathCount else [0, 0]