LeetCode 题解工作台
最大得分的路径数目
给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。 你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X' 。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。 一条路径的 「得分」…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示从起点 $(n - 1, n - 1)$ 到达 $(i, j)$ 的最大得分，定义 表示从起点 $(n - 1, n - 1)$ 到达 $(i, j)$ 的最大得分的方案数。初始时 $f[n - 1][n - 1] = 0$，并且 $g[n - 1][n - 1] = 1$。其它位置的 均为 ，而 均为 。 对于当前位置 $(i, j)$，它可以由 $(i + 1, j)$,…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个正方形字符数组 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
解题思路
方法一：动态规划
我们定义 表示从起点 到达 的最大得分，定义 表示从起点 到达 的最大得分的方案数。初始时 ，并且 。其它位置的 均为 ，而 均为 。
对于当前位置 ，它可以由 , , 三个位置转移而来，因此我们可以枚举这三个位置，更新 和 的值。如果当前位置 有障碍，或者当前位置是起点，或者其它位置越界，则不进行更新。否则，如果其它位置 满足 ，那么我们更新 ，并且 。如果 ，那么我们更新 。最后，如果当前位置 可达并且是数字，我们更新 。
最后，如果 ，说明没有路径可以到达终点，返回 。否则，返回 。注意，返回结果需要对 取余。
时间复杂度 ，空间复杂度 。其中 是数组的边长。
class Solution:
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
def update(i, j, x, y):
if x >= n or y >= n or f[x][y] == -1 or board[i][j] in "XS":
return
if f[x][y] > f[i][j]:
f[i][j] = f[x][y]
g[i][j] = g[x][y]
elif f[x][y] == f[i][j]:
g[i][j] += g[x][y]
n = len(board)
f = [[-1] * n for _ in range(n)]
g = [[0] * n for _ in range(n)]
f[-1][-1], g[-1][-1] = 0, 1
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
update(i, j, i + 1, j)
update(i, j, i, j + 1)
update(i, j, i + 1, j + 1)
if f[i][j] != -1 and board[i][j].isdigit():
f[i][j] += int(board[i][j])
mod = 10**9 + 7
return [0, 0] if f[0][0] == -1 else [f[0][0], g[0][0] % mod]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) since each cell is processed once and each has at most three neighbors. Space complexity is O(n^2) for the DP table, but can be reduced to O(n) by storing only the current and previous row. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can you define a DP state that tracks both sum and count together?
- question_mark
How do you handle obstacles in the dynamic programming transition?
- question_mark
What edge cases cause path count to be zero despite numeric values on the board?
常见陷阱
外企场景- error
Counting paths from neighbors that do not contribute to max_sum, inflating path counts.
- error
Failing to initialize the starting cell or obstacles correctly, causing DP propagation errors.
- error
Ignoring the modulo requirement for path counts, leading to integer overflow.
进阶变体
外企场景- arrow_right_alt
Allow moves in all four directions, changing the state transition rules.
- arrow_right_alt
Compute minimum score paths instead of maximum, requiring adjustment in comparison logic.
- arrow_right_alt
Use larger boards with more obstacles, testing space optimization strategies.