难度: Hard
给你一个正方形字符数组 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运行时间: 66 ms
内存: 17.5 MB
class Solution:
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
# 好像很有道理... 只有下方和右方的双最大值、才能加起来得到最大值... 所以居然可以由两边唯一确定，不用去记录其他的 scores 了...
# DP[i][j]: 从右下角走到当前的 (score, ways)
# DP[i][j] = max(DP[i+1][j],
# DP[i][j+1],
# DP[i+1][j+1]) + grid[i][j]
# 如果相同：合并 ways.
n = len(board)
dp = [[(-inf, -inf)] * n for _ in range(n)] # <score, ways>
# 递归基.
dp[-1][-1] = (0, 1)
for i in range(n-2, -1, -1):
dp[i][-1] = (dp[i+1][-1][0] + int(board[i][-1]) if board[i][-1] != 'X' else -inf, dp[i+1][-1][1])
for j in range(n-2, -1, -1):
dp[-1][j] = (dp[-1][j+1][0] + int(board[-1][j]) if board[-1][j] != 'X' else -inf, dp[-1][j+1][1])
for i in range(n-2, -1, -1):
for j in range(n-2, -1, -1):
if board[i][j] == 'X':
continue
cur_score = (int(board[i][j]) if board[i][j] != 'E' else 0)
a1, b1 = dp[i+1][j]
a2, b2 = dp[i][j+1]
a3, b3 = dp[i+1][j+1]
mx_score = max(a1, a2, a3)
ways = (b1 if a1 == mx_score else 0) + \
(b2 if a2 == mx_score else 0) + \
(b3 if a3 == mx_score else 0)
dp[i][j] = (mx_score + cur_score, ways)
MOD = 10 ** 9 + 7
return [0,0] if dp[0][0][0] == -inf else [dp[0][0][0] % MOD, dp[0][0][1] % MOD]
该题解使用动态规划的方法求解。dp[i][j]存储从(i, j)到终点的最大得分和对应的路径数。对于每个位置(i, j)，我们考虑从下方、右方和右下方三个方向来的路径，取这三个方向中得分最高的路径，如果有多条路径得分相同，则将它们的路径数相加。最终，dp[0][0]就存储了从起点到终点的最大得分和对应的路径数。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
n = len(board)
dp = [[(-float('inf'), -float('inf'))] * n for _ in range(n)] # <score, ways>
dp[-1][-1] = (0, 1) # Base case
for i in range(n-2, -1, -1):
dp[i][-1] = (dp[i+1][-1][0] + int(board[i][-1]) if board[i][-1] != 'X' else -float('inf'), dp[i+1][-1][1])
for j in range(n-2, -1, -1):
dp[-1][j] = (dp[-1][j+1][0] + int(board[-1][j]) if board[-1][j] != 'X' else -float('inf'), dp[-1][j+1][1])
for i in range(n-2, -1, -1):
for j in range(n-2, -1, -1):
if board[i][j] == 'X':
continue
cur_score = (int(board[i][j]) if board[i][j] != 'E' else 0)
a1, b1 = dp[i+1][j]
a2, b2 = dp[i][j+1]
a3, b3 = dp[i+1][j+1]
mx_score = max(a1, a2, a3)
ways = (b1 if a1 == mx_score else 0) + \
(b2 if a2 == mx_score else 0) + \
(b3 if a3 == mx_score else 0)
dp[i][j] = (mx_score + cur_score, ways)
MOD = 10 ** 9 + 7
return [0,0] if dp[0][0][0] == -float('inf') else [dp[0][0][0] % MOD, dp[0][0][1] % MOD]
在动态规划中，将dp数组的初始值设为负无穷是为了正确处理没有可行路径的情况。负无穷作为初始值可以确保在进行最大值比较时，任何非负无穷的实际得分都会被选中，而且可以区分未被更新（无法到达的点）和得分低的路径。如果初始化为0或其他正常值，可能会导致错误地将没有路径的点计入有效路径中，或者错误地处理得分计算。
在dp数组中，对于元组(score, ways)，当遇到障碍或没有路径时，理论上应将ways设置为0，因为从该位置无法到达终点，故不存在任何路径。然而，在题解中使用负无穷主要是为了配合score的负无穷值，以此来统一处理无效状态。实际应用中，应将ways设为0，更直观地反映'无路径'的状态。
题解中的更新策略是从终点向起点反向计算，因此每个点的状态仅由其下方、右方和右下方的点决定，这些方向在反向逻辑下代表'来自'的方向。如果从左上方、上方或左方更新，那将意味着在正向逻辑中处理状态，这与题解中使用的反向动态规划策略不符。反向动态规划使得初始条件设置在终点处，从而可以有效地根据题目要求计算从起点到终点的最大得分和路径数。
在题目中，起点'E'表示起点，而在路径得分计算中，起点的得分设为0是因为起点不应该给予额外的得分。将'E'的得分设为0是为了确保在计算从起点到终点的得分时，不会错误地增加起始位置的得分，这有助于准确地反映路径的实际得分。这样的处理确保了起点只是路径的开始，并不对得分产生影响。