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
解题思路
这是一道经典的动态规划问题，需要同时求解最大得分和方案数。
核心思路：
状态定义：使用两个二维数组
dp和waysdp[i][j]表示从起点 ‘S’ 到位置(i,j)能获得的最大得分ways[i][j]表示达到最大得分dp[i][j]的路径数量
转移方向：从右下角的 ‘S’ 开始，只能向上、向左或左上方移动，所以我们反向思考，从左上角 ‘E’ 开始动态规划到右下角 ‘S’
状态转移：对于每个位置
(i,j)，可以从三个方向转移而来：- 右方
(i, j+1) - 下方
(i+1, j) - 右下方
(i+1, j+1)
- 右方
转移逻辑：
- 找出三个来源中的最大得分
- 如果最大得分相同，累加方案数
- 如果遇到障碍 ‘X’，该位置不可达
边界处理：起点 ‘E’ 得分为0，方案数为1；终点 ‘S’ 不计入得分
时间复杂度：O(n²)，需要遍历整个棋盘 空间复杂度：O(n²)，使用两个二维数组存储状态
代码实现
class Solution {
public:
vector<int> pathsWithMaxScore(vector<string>& board) {
int n = board.size();
const int MOD = 1e9 + 7;
vector<vector<int>> dp(n, vector<int>(n, -1));
vector<vector<int>> ways(n, vector<int>(n, 0));
dp[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--) {
if (board[i][j] == 'X' || (i == n-1 && j == n-1)) continue;
int maxScore = -1;
int totalWays = 0;
// 从右方来
if (j + 1 < n && dp[i][j+1] != -1) {
int score = dp[i][j+1];
if (board[i][j] != 'E') score += board[i][j] - '0';
if (score > maxScore) {
maxScore = score;
totalWays = ways[i][j+1];
} else if (score == maxScore) {
totalWays = (totalWays + ways[i][j+1]) % MOD;
}
}
// 从下方来
if (i + 1 < n && dp[i+1][j] != -1) {
int score = dp[i+1][j];
if (board[i][j] != 'E') score += board[i][j] - '0';
if (score > maxScore) {
maxScore = score;
totalWays = ways[i+1][j];
} else if (score == maxScore) {
totalWays = (totalWays + ways[i+1][j]) % MOD;
}
}
// 从右下方来
if (i + 1 < n && j + 1 < n && dp[i+1][j+1] != -1) {
int score = dp[i+1][j+1];
if (board[i][j] != 'E') score += board[i][j] - '0';
if (score > maxScore) {
maxScore = score;
totalWays = ways[i+1][j+1];
} else if (score == maxScore) {
totalWays = (totalWays + ways[i+1][j+1]) % MOD;
}
}
if (maxScore != -1) {
dp[i][j] = maxScore;
ways[i][j] = totalWays;
}
}
}
return dp[0][0] == -1 ? vector<int>{0, 0} : vector<int>{dp[0][0], ways[0][0]};
}
};
class Solution:
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
n = len(board)
MOD = 10**9 + 7
dp = [[-1] * n for _ in range(n)]
ways = [[0] * n for _ in range(n)]
dp[n-1][n-1] = 0
ways[n-1][n-1] = 1
for i in range(n-1, -1, -1):
for j in range(n-1, -1, -1):
if board[i][j] == 'X' or (i == n-1 and j == n-1):
continue
max_score = -1
total_ways = 0
directions = [(0, 1), (1, 0), (1, 1)]
for di, dj in directions:
ni, nj = i + di, j + dj
if ni < n and nj < n and dp[ni][nj] != -1:
score = dp[ni][nj]
if board[i][j] != 'E':
score += int(board[i][j])
if score > max_score:
max_score = score
total_ways = ways[ni][nj]
elif score == max_score:
total_ways = (total_ways + ways[ni][nj]) % MOD
if max_score != -1:
dp[i][j] = max_score
ways[i][j] = total_ways
return [0, 0] if dp[0][0] == -1 else [dp[0][0], ways[0][0]]
public class Solution {
public int[] PathsWithMaxScore(IList<string> board) {
int n = board.Count;
int MOD = 1000000007;
int[,] dp = new int[n, n];
int[,] ways = new int[n, n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i, j] = -1;
}
}
dp[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--) {
if (board[i][j] == 'X' || (i == n-1 && j == n-1)) continue;
int maxScore = -1;
int totalWays = 0;
int[,] directions = {{0, 1}, {1, 0}, {1, 1}};
for (int d = 0; d < 3; d++) {
int ni = i + directions[d, 0];
int nj = j + directions[d, 1];
if (ni < n && nj < n && dp[ni, nj] != -1) {
int score = dp[ni, nj];
if (board[i][j] != 'E') {
score += board[i][j] - '0';
}
if (score > maxScore) {
maxScore = score;
totalWays = ways[ni, nj];
} else if (score == maxScore) {
totalWays = (totalWays + ways[ni, nj]) % MOD;
}
}
}
if (maxScore != -1) {
dp[i, j] = maxScore;
ways[i, j] = totalWays;
}
}
}
return dp[0, 0] == -1 ? new int[]{0, 0} : new int[]{dp[0, 0], ways[0, 0]};
}
}
var pathsWithMaxScore = function(board) {
const MOD = 1e9 + 7;
const n = board.length;
// dp[i][j] = [maxScore, numPaths]
const dp = Array(n).fill().map(() => Array(n).fill().map(() => [-1, 0]));
// Start from bottom right (S)
dp[n-1][n-1] = [0, 1];
// Fill dp table from bottom-right to top-left
for (let i = n - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
if (board[i][j] === 'X' || (i === n-1 && j === n-1)) continue;
let maxScore = -1;
let paths = 0;
// Check three directions: right, down, down-right
const directions = [[0, 1], [1, 0], [1, 1]];
for (let [di, dj] of directions) {
const ni = i + di;
const nj = j + dj;
if (ni < n && nj < n && dp[ni][nj][0] !== -1) {
const score = dp[ni][nj][0];
const count = dp[ni][nj][1];
if (score > maxScore) {
maxScore = score;
paths = count;
} else if (score === maxScore) {
paths = (paths + count) % MOD;
}
}
}
if (maxScore !== -1) {
const cellValue = board[i][j] === 'E' ? 0 : parseInt(board[i][j]);
dp[i][j] = [maxScore + cellValue, paths];
}
}
}
return dp[0][0][0] === -1 ? [0, 0] : dp[0][0];
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n²) | 遍历 n×n 的棋盘，每个位置考虑3个转移方向 |
| 空间复杂度 | O(n²) | 使用两个 n×n 的二维数组存储状态 |