LeetCode 1301. 最大得分的路径数目
题目描述
题意分析
从正方形棋盘右下角的
S出发，每步只能向上、向左或向左上走，最终到左上角的E，不能进入障碍X。经过数字格时累加其数值，起点和终点不加分。返回两项：所有合法路径的最大得分，以及恰好取得这个最大分数的路径条数。只有条数对
10^9 + 7取模，分数保持原值；无路可走时返回[0, 0]，不能与可达但得分为零的情况混淆。
解法：DP 求最大分数与路径数
核心思路
[!blue]
每步都会减小行号或列号，路径不会回到之前的位置，因此可以按依赖顺序做动态规划。用
score[i][j]保存从S到当前格的最大得分，ways[i][j]保存达到这个得分的路径数；只保存条数无法分辨哪些路径最优，只保存分数又无法回答第二项。当前格的最后一步只能来自它的下方、右方或右下方。选择这些可达前驱中的最高分，再加当前数字格的分值，就得到当前最优分数。到同一个格子的较低分路径可以放弃，因为以后能走的后缀完全相同，它不可能追上已经更高分的前缀。
比较前驱时，如果发现更高分，就替换
best并把计数重置为该前驱的最优路径数；如果分数与当前最佳相同，才累加计数。来自不同前驱的路径最后一步不同，属于不同路径，因此并列最优数量可以直接相加，不会重复。用
score = -1表示不可达，避免把合法零分误判为空路径。起点设为分数零、条数一，表示已经位于起点的一种起始状态；障碍和不可达前驱都不参与转移。行和列都从大到小扫描，确保三个前驱先完成。得到前驱最优值后，数字格再加自身分数，
E不加分，已初始化的S直接跳过。判断是否可达看score，不能看取模后的路径数是否为零。
解题步骤
- 分数表全部初始化为负一，计数表为零，右下起点设为
(0, 1)。- 倒序遍历行和列，跳过障碍及起点。
- 检查下、右、右下三个合法且可达的前驱，更优时重置计数，同优时累加并取模。
- 若没有可达前驱，当前格继续保持不可达；否则加上当前数字分值并写入两项状态。
- 终点分数为负一时返回
[0, 0]，否则返回终点最优分数与对应路径数。
代码实现
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) {
// 用 -1 区分不可达与合法零分。
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;
// 起点已跳过，终点 E 也不能按数字计分。
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++ {
// 用 -1 区分不可达与合法零分。
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
// 起点已跳过，终点 E 也不能按数字计分。
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²)$，每个格子检查三个前驱。
- 空间复杂度：$O(n²)$，保存分数和计数。
关键点总结
[!green]
- 每格同时保存最优值与达到最优值的数量，两者按同一个比较结果更新。
- 更优前驱会淘汰之前的次优计数，同优前驱才相加。
- 不可达、合法零分、取模后零条数是不同概念，使用分数哨兵区分。
- 只对计数取模，分数用于真实大小比较。
易错点总结
[!yellow]
- 更优时仍累加旧方案：会混入次优路径。
- 起点计数没有设为 1：所有后继都没有计数来源。
- 把 E 当数字处理：会凭空增加分数。
- 以取模后的 ways=0 判断不可达：可达路径数也可能恰好为模数倍数，应看 score。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 673. 最长递增子序列的个数 | 中等 | 同样同时维护最优值与达到最优值的方案数，遇到同分前驱要累加次数。 |
| 64. 最小路径和 | 中等 | 网格路径DP是基础，本题取最大得分并统计最优路径，且允许额外的对角移动。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！