Problem statement

https://leetcode.com/problems/number-of-paths-with-max-score/

Solution

The idea is to keep dp with two states: dp(i, j) will return tuple: maximum score when we reach cell (i, j) and number of ways in which we did it. Then to evaluate dp(i, j) we need to look at all 3 neighbours and choose among them such that which have the biggest score: it can happen that one of them have biggest score, like [10, 8, 12] or it can happen that two or three as well, like [10, 12, 12] or [12, 12, 12]. Number of ways calculated as sum of all numbers of ways for values with biggest score.

Complexity

Time and space complexity is O(n^2).

Code

class Solution:
    def pathsWithMaxScore(self, board):
        n, MOD = len(board), 10**9 + 7
        board[-1] = board[-1][:-1] + "0"

        @lru_cache(None)
        def dp(i, j):
            if i == 0 and j == 0: return (0, 1)
            if i < 0 or j < 0 or board[i][j] == "X": return (-float("inf"), 1)
            sc = [dp(i - 1, j), dp(i, j - 1), dp(i-1, j-1)]  
            max_s = max(sc[0][0], sc[1][0], sc[2][0])
            s_new = max_s + int(board[i][j])
            c_new = sum(sc[i][1] for i in range(3) if sc[i][0] == max_s) % MOD
            return (s_new, c_new)
      
        t, q = dp(n-1, n-1)
        return [t, q] if t != -float("inf") else [0, 0]