LeetCode 1301. 最大得分的路径数目

Categories:

题目描述
思路分析
1. 解法一：DP 求最大分数与路径数（推荐）
相似题目

题目描述

✅ 1301. 最大得分的路径数目

思路分析

解法一：DP 求最大分数与路径数（推荐）

核心思路：

从终点 S 逆推到起点 E，每格可由右、下、右下到达。

维护两个 DP：score[i][j] 为最大分数，ways[i][j] 为达到最大分数的路径数。

若三邻居最大分数为 -1 表示不可达，否则取最大并累加对应路径数。

复杂度分析：

时间复杂度：O(n^2)，其中 n 为棋盘边长。

空间复杂度：O(n^2)。

class Solution {
    private static final int MOD = 1_000_000_007;

    public int[] pathsWithMaxScore(java.util.List<String> board) {
        int n = board.size();
        int[][] score = new int[n][n];
        int[][] ways = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                score[i][j] = -1;
            }
        }
        score[n - 1][n - 1] = 0;
        ways[n - 1][n - 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;
                int[][] dirs = {{1, 0}, {0, 1}, {1, 1}};
                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 = (c == 'E') ? 0 : (c - '0');
                score[i][j] = best + add;
                ways[i][j] = cnt;
            }
        }

        if (score[0][0] == -1) {
            return new int[] {0, 0};
        }
        return 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]}
}

相似题目

题目	难度	考察点
63. 不同路径 II	中等	DP
62. 不同路径	中等	DP
64. 最小路径和	中等	DP
1289. 下降路径最小和 II	困难	DP
221. 最大正方形	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/42544811