Leetcode 1301：最大得分的路径数目（超详细的解法！！！）

给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。

你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。

一条路径的 「得分」 定义为：路径上所有数字的和。

请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。

如果没有任何路径可以到达终点，请返回 [0, 0] 。

示例 1：

输入：board = ["E23","2X2","12S"]
输出：[7,1]

示例 2：

输入：board = ["E12","1X1","21S"]
输出：[4,2]

示例 3：

输入：board = ["E11","XXX","11S"]
输出：[0,0]

提示：

• 2 <= board.length == board[i].length <= 100

解题思路

这个问题和之前问题

Leetcode 62：不同路径（最详细的解法！！！）

Leetcode 64：最小路径和（最详细的解法！！！）

Leetcode 1102：得分最高的路径（超详细的解法！！！）

所以可以想到通过dfs加记忆化的方式来做，定义函数$f(x,y)$f(x,y)的返回结果是从x,y出发到达0,0点的最大得分maxv和相应的路径数目cnt。那么对于maxv来说：

• $maxv(x,y)=max(maxv(x-1,y),maxv(x,y-1),maxv(x-1,y-1))$maxv(x,y)=max(maxv(x−1,y),maxv(x,y−1),maxv(x−1,y−1))

对于cnt来说，我们需要判断x,y节点的值curv和右边、下边和右下哪些值恰好是maxv(x,y)，那么：

• $cnt(x,y)=\sum(cnt(x-1,y),cnt(x,y-1),cnt(x-1,y-1))+curv$cnt(x,y)=∑(cnt(x−1,y),cnt(x,y−1),cnt(x−1,y−1))+curv

注意，需要判断cnt(x-1,y)、cnt(x,y-1)和cnt(x-1,y-1)哪些是满足curv+cnt(...)==maxv(x,y)的。

最后考虑边界条件，当x==0 && y==0，返回[0,1]；如果x和y不在边界或者x,y的点是'X'的话，返回[-10**5, 0]。

from functools import lru_cache
class Solution:
    def pathsWithMaxScore(self, b: List[str]) -> List[int]:
        r, c, mod = len(b), len(b[0]), 10**9 + 7
        
        @lru_cache(None)
        def dfs(x, y):
            if x < 0 or x >= r or y < 0 or y >= c or b[x][y] == 'X':
                return [-10**5, 0]
            
            if x == 0 and y == 0:
                return [0, 1]
            
            res = []
            for i, j in [[-1, 0], [0, -1], [-1, -1]]:
                res.append(dfs(i + x, j + y))
                
            curv = (int(b[x][y]) if b[x][y] != 'S' else 0)
            maxv, cnt = curv + max([v[0] for v in res]), 0
            for v in res:
                if v[0] + curv == maxv:
                    cnt += v[1]
            return [maxv, cnt % mod]
        
        t = dfs(r - 1, c - 1)
        return t if t[1] != 0 else [0, 0]

当然也可以采用动态规划的写法，思路是一样的。

class Solution:
    def pathsWithMaxScore(self, A):
        n, mod = len(A), 10**9 + 7
        dp = [[[-10**5, 0] for _ in range(n + 1)] for _ in range(n + 1)]
        dp[n - 1][n - 1] = [0, 1]
        
        for x in range(n-1, -1, -1):
            for y in range(n-1, -1, -1):
                if A[x][y] in 'XS': 
                    continue
                    
                for i, j in [[0, 1], [1, 0], [1, 1]]:
                    if dp[x][y][0] < dp[x + i][y + j][0]:
                        dp[x][y] = [dp[x + i][y + j][0], 0]
                    if dp[x][y][0] == dp[x + i][y + j][0]:
                        dp[x][y][1] += dp[x + i][y + j][1]
                dp[x][y][0] += int(A[x][y]) if x or y else 0
                
        return [dp[0][0][0] if dp[0][0][1] else 0, dp[0][0][1] % mod]

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！