LeetCode 1301. 最大得分的路径数目
目录
题目描述
题意分析
给定一个
n × n的字符方阵board，左上角board[0][0]是'E'（终点），右下角board[n-1][n-1]是'S'（起点），其余格子要么是'1'..'9'的数字，要么是障碍'X'。从S出发，每步只能往上、左、左上三个方向之一移动，走到E为止，途中不能踩障碍。路径得分是沿途所有数字格之和（S和E本身不计分）。要返回两个数：最大得分，以及取到最大得分的路径条数（对 $10^9+7$ 取模）；如果S根本走不到E，返回[0, 0]。这道题要求的是两个耦合的量：最优值和最优值的方案数。方案数只在最优值上统计，不是所有路径都算，这决定了不能把两个量拆成两次独立求解——必须在同一次推进里同时维护。
约束给出
n ≤ 100，格子总数最多一万，而路径条数却要取模，说明路径数量是指数级的。这两条合在一起是很强的信号：不能枚举路径，只能按格子递推，让每个格子的结果被后面的格子复用。移动方向只有三个且全部朝着行、列下标减小的方向，意味着「从哪来」的关系是一张有向无环图，格子之间没有循环依赖，可以按下标顺序一次遍历算完。
边界要留意四点：
E和S不贡献分数；X既不能作为落脚点也不能作为中转；出发格S的初始得分是 0 而不是 -1；无路可走时答案是[0, 0]而不是[-1, 0]，也不是抛异常。还要区分「得分为 0」和「不可达」：某条路径可能恰好只经过
E、S相邻的格子而得分很小，但绝不会因此变成不可达。所以需要一个和任何合法得分都不冲突的哨兵值来表示不可达。
解法：DP 求最大分数与路径数
核心思路
把棋盘看成一张有向无环图，同时维护最优得分和达到该得分的方案数：
score[i][j]：从S到(i,j)的合法路径最大得分，包含当前数字格；-1表示不可达。ways[i][j]：达到score[i][j]的路径数量，按 $10^9+7$ 取模。从
S到(i,j)的最后一步只能来自(i+1,j)、(i,j+1)、(i+1,j+1)。因此从右下向左上遍历，在三个已计算的前驱中找最大score：遇到更大值时替换最大值并重置方案数；遇到并列最大值时累加方案数；不可达前驱不参与转移。基例为
score[S]=0, ways[S]=1。S上的空路径是所有计数的来源；E和S都不加分。若某格没有可达前驱，就继续保持score=-1, ways=0。不变量：处理
(i,j)时，它的三个前驱状态均已最终确定；score/ways精确描述从S到这些格子的最大得分及对应数量。正确性：任意到达
(i,j)的路径都有唯一的最后一个前驱。归纳假设保证三个前驱状态正确，取最大值会排除次优路径，只对并列最优前驱求和则不重不漏地统计所有最优路径。按依赖顺序推进到E后即得到全局答案。
解题步骤
- 将
score全部填为-1，ways默认为 0；设置右下角S的状态为(0,1)。- 行、列都从大到小遍历，跳过障碍和已经初始化的
S。- 检查下、右、右下三个前驱。更优时重置计数，并列时累加后取模。
- 若没有可达前驱，当前格保持不可达；否则加上当前数字，写入两个状态。
- 左上角仍不可达时返回
[0,0]，否则返回其最大得分和方案数。样例
['E23','2X2','12S']最优路径得分为2+3+2=7，且只有一条，返回[7,1]。['E12','1X1','21S']有两条最优路径，返回[4,2]。不可达反例
['E11','XXX','11S']必须返回[0,0]。它能检验score=-1哨兵、障碍跳过和最终包装是否一致。
代码实现
import java.util.Arrays;
import java.util.List;
class Solution {
private static final int MOD = 1_000_000_007;
public int[] pathsWithMaxScore(List<String> board) {
int n = board.size();
int[][] score = new int[n][n];
int[][] ways = new int[n][n];
for (int[] row : score) {
Arrays.fill(row, -1);
}
score[n - 1][n - 1] = 0;
ways[n - 1][n - 1] = 1;
int[][] dirs = {{1, 0}, {0, 1}, {1, 1}};
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
char c = board.get(i).charAt(j);
if (c == 'X' || (i == n - 1 && j == n - 1)) {
continue;
}
int best = -1;
int cnt = 0;
for (int[] d : dirs) {
int ni = i + d[0];
int nj = j + d[1];
if (ni >= n || nj >= n || score[ni][nj] == -1) {
continue;
}
int val = score[ni][nj];
if (val > best) {
best = val;
cnt = ways[ni][nj];
} else if (val == best) {
cnt = (cnt + ways[ni][nj]) % MOD;
}
}
if (best == -1) {
continue;
}
int add = 0;
if (c != 'E') {
add = c - '0';
}
score[i][j] = best + add;
ways[i][j] = cnt;
}
}
return score[0][0] == -1
? new int[]{0, 0}
: new int[]{score[0][0], ways[0][0]};
}
}
func pathsWithMaxScore(board []string) []int {
const mod = 1000000007
n := len(board)
score := make([][]int, n)
ways := make([][]int, n)
for i := 0; i < n; i++ {
score[i] = make([]int, n)
ways[i] = make([]int, n)
for j := 0; j < n; j++ {
score[i][j] = -1
}
}
score[n-1][n-1] = 0
ways[n-1][n-1] = 1
dirs := [][]int{{1, 0}, {0, 1}, {1, 1}}
for i := n - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
c := board[i][j]
if c == 'X' || (i == n-1 && j == n-1) {
continue
}
best := -1
cnt := 0
for _, d := range dirs {
ni := i + d[0]
nj := j + d[1]
if ni >= n || nj >= n || score[ni][nj] == -1 {
continue
}
val := score[ni][nj]
if val > best {
best = val
cnt = ways[ni][nj]
} else if val == best {
cnt += ways[ni][nj]
if cnt >= mod {
cnt -= mod
}
}
}
if best == -1 {
continue
}
add := 0
if c != 'E' {
add = int(c - '0')
}
score[i][j] = best + add
ways[i][j] = cnt
}
}
if score[0][0] == -1 {
return []int{0, 0}
}
return []int{score[0][0], ways[0][0]}
}
复杂度分析
- 时间复杂度：$O(n^2)$，每个格子只检查三个前驱。
- 空间复杂度：$O(n^2)$，用于最大得分和方案数两个状态表。
关键点总结
- 状态必须明确为“从
S到当前格”，这样三个依赖格就是它在原移动方向上的前驱。- 最优值与最优方案数同步转移：更优就重置，相等才累加。
-1区分不可达和合法的 0 分；不可达状态不能参与比较或计数。ways[S]=1是计数基例，方案数每次相加后取模，得分不取模。- 遍历方向必须保证下、右、右下三个状态已计算完成。
易错点总结
- 把状态误定义为“当前格到
E”，却仍读取下、右、右下：状态含义与依赖方向矛盾。score默认填 0：不可达反例会沿障碍两侧生成正分、零方案的伪状态；必须使用-1。- 忘记
ways[S]=1：所有后续方案数都会保持 0。- 遇到更优前驱仍累加旧计数：次优路径会混进答案；更优时必须重置。
- 并列最优不累加，或累加后不取模：分别会漏计或整数溢出。
- 把
E当数字计算c-'0'：样例会凭空增加 21 分。- 不可达时直接返回内部状态：会返回
[-1,0]，而题目要求[0,0]。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 62. 不同路径 | 中等 | 只数方案数、没有最优值，转移退化成单纯的加法 |
| 63. 不同路径 II | 中等 | 在纯计数基础上加障碍，障碍格方案数置 0 即可，无需哨兵区分不可达 |
| 64. 最小路径和 | 中等 | 只求最优值不计数，ways 那一半可以整个删掉 |
| 120. 三角形最小路径和 | 中等 | 网格换成三角形，每层下标范围随行变化，转移只有两个后继 |
| 174. 地下城游戏 | 困难 | 状态必须定义成「所需初始血量」而非「累计血量」，否则贪心方向错误 |
| 688. 骑士在棋盘上的概率 | 中等 | 多一维步数，转移是概率求和而非取最大，八个方向且允许走出棋盘 |
| 931. 下降路径最小和 | 中等 | 逐行推进、每格看上一行三个邻居，只求最优值，可原地滚动 |
| 980. 不同路径 III | 困难 | 要求走遍所有空格，无法用 DP 坍缩，必须回溯 + 状态压缩 |
| 1289. 下降路径最小和 II | 困难 | 转移是「上一行除同列外的最小值」，需要用最小与次小值把 $O(n)$ 转移降到 $O(1)$ |
| 1594. 矩阵的最大非负积 | 中等 | 负数乘法会翻转大小关系，必须同时维护最大与最小两个状态 |
| LCR 098. 不同路径 | 中等 | 与 62 同题，可用组合数 $C_{m+n-2}^{m-1}$ 直接秒杀 |
| LCR 099. 最小路径和 | 中等 | 与 64 同题，适合练一维滚动数组的写法 |
| LCR 100. 三角形最小路径和 | 中等 | 与 120 同题，自底向上推可以省掉边界特判 |
| 剑指 Offer 47. 礼物的最大价值 | 中等 | 只能右和下两个方向求最大和，是本题去掉计数与斜向后的最简版本 |