class Solution {
public:
vector<int> pathsWithMaxScore(vector<string>& board) {
}
};
1301. 最大得分的路径数目
给你一个正方形字符数组 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原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 4.5 MB, 提交时间: 2023-09-18 15:16:18
func pathsWithMaxScore(board []string) []int {
// 获取二维数组的行m (长度) 和 列n (宽度)
m, n := len(board), len(board[0])
// dp[i][j] 表示从位置(i,j) 到终点的最大得分
// path[i][j] 存储从位置(i, j) 到终点获得最大得分的方案数
dp, path := make([][]int, m), make([][]int, m)
// 对结果取模的值
mod := int(1e9 + 7)
// 初始化动态规划表
for i := range dp {
dp[i], path[i] = make([]int, n), make([]int, n)
}
// 初始条件：计算底部和最右边界值 分数0 方案数1
dp[m-1][n-1], path[m-1][n-1] = 0, 1
// 计算最后一列的dp值和path值
for i := m - 2; i >= 0 && board[i][n-1] != 'X'; i-- {
dp[i][n-1] = dp[i+1][n-1] + int(board[i][n-1]-'0')
path[i][n-1] = 1
}
// 计算最后一行的dp值和path值
for j := n - 2; j >= 0 && board[m-1][j] != 'X'; j-- {
dp[m-1][j] = dp[m-1][j+1] + int(board[m-1][j]-'0')
path[m-1][j] = 1
}
// 状态转移：从右下角向左上角遍历，对每个点计算最大分数和路径数量
for i := m - 2; i >= 0; i-- {
for j := n - 2; j >= 0; j-- {
// 如果当前位置是障碍物，则跳过
if board[i][j] == 'X' {
continue
}
// 如果三个方向都不可达，则跳过
if path[i+1][j] ==0 && path[i][j+1]==0 && path[i+1][j+1]==0{
continue
}
// 获取当前位置的值。如果当前位置是 'E'，则值为0
score := int(board[i][j]-'0')
if board[i][j] == 'E'{
score = 0
}
// 更新dp表和path表
maxPreScore := max(dp[i+1][j], dp[i][j+1], dp[i+1][j+1])
dp[i][j] = maxPreScore + score
// 根据哪个方向得到的最大值，更新路径数量
if maxPreScore == dp[i+1][j] {
path[i][j] = path[i+1][j] % mod
}
if maxPreScore == dp[i][j+1] {
path[i][j] += path[i][j+1] % mod
}
if maxPreScore == dp[i+1][j+1] {
path[i][j] += path[i+1][j+1] % mod
}
// 对路径数量取模，避免溢出
path[i][j] %= mod
}
}
// 最后返回dp表和path表的起点，即得分最大值和方案数
return []int{dp[0][0], path[0][0]}
}
func max(arr ...int) int {
ans := arr[0]
for _, num := range arr {
if num > ans { ans = num }
}
return ans
}
java 解法, 执行用时: 11 ms, 内存消耗: 42.6 MB, 提交时间: 2023-09-18 15:13:07
/**
* 方便起见，从左上角往右下角进行状态转移，这样写起来更顺手一些。
* dp[i][j][0]为从左上角到位置（i, j）的最大得分。
* dp[i][j][1]为从左上角到位置（i, j）的最大得分的路径数。
*/
class Solution {
static final int MOD = 1000000007;
int[] dx = new int[]{-1, -1, 0};
int[] dy = new int[]{0, -1, -1};
public int[] pathsWithMaxScore(List<String> board) {
int m = board.size();
int n = board.get(0).length();
int[][][] dp = new int[m][n][2];
dp[0][0][0] = 0;
dp[0][0][1] = 1;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
char c = board.get(i).charAt(j);
if (c == 'X'){
dp[i][j][0] = Integer.MIN_VALUE;
dp[i][j][1] = 0;
}
}
}
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
char c = board.get(i).charAt(j);
if (!Character.isDigit(c) && !(i == m - 1 && j == n - 1)) continue;
int val = (i == m - 1 && j == n - 1) ? 0 : (c - '0');
int maxScore = Integer.MIN_VALUE;
int maxScoreCount = 0;
for (int k = 0; k < dx.length; k++){
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && dp[x][y][0] > maxScore){
maxScore = dp[x][y][0];
maxScoreCount = dp[x][y][1];
}
else if (x >= 0 && x < m && y >= 0 && y < n && dp[x][y][0] == maxScore){
maxScoreCount += dp[x][y][1];
maxScoreCount %= MOD;
}
}
dp[i][j][0] = (maxScore == Integer.MIN_VALUE) ? Integer.MIN_VALUE : (maxScore + val);
dp[i][j][1] = maxScoreCount;
}
}
return dp[m-1][n-1][0] == Integer.MIN_VALUE ? new int[]{0, 0} : dp[m-1][n-1];
}
}
cpp 解法, 执行用时: 16 ms, 内存消耗: 9.1 MB, 提交时间: 2023-09-18 15:12:15
using PII = pair<int, int>;
class Solution {
private:
static constexpr int mod = (int)1e9 + 7;
public:
void update(vector<vector<PII>>& dp, int n, int x, int y, int u, int v) {
if (u >= n || v >= n || dp[u][v].first == -1) {
return;
}
if (dp[u][v].first > dp[x][y].first) {
dp[x][y] = dp[u][v];
}
else if (dp[u][v].first == dp[x][y].first) {
dp[x][y].second += dp[u][v].second;
if (dp[x][y].second >= mod) {
dp[x][y].second -= mod;
}
}
}
vector<int> pathsWithMaxScore(vector<string>& board) {
int n = board.size();
vector<vector<PII>> dp(n, vector<PII>(n, {-1, 0}));
dp[n - 1][n - 1] = {0, 1};
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (!(i == n - 1 && j == n - 1) && board[i][j] != 'X') {
update(dp, n, i, j, i + 1, j);
update(dp, n, i, j, i, j + 1);
update(dp, n, i, j, i + 1, j + 1);
if (dp[i][j].first != -1) {
dp[i][j].first += (board[i][j] == 'E' ? 0 : board[i][j] - '0');
}
}
}
}
return dp[0][0].first == -1 ? vector<int>{0, 0} : vector<int>{dp[0][0].first, dp[0][0].second};
}
};
python3 解法, 执行用时: 156 ms, 内存消耗: 17.6 MB, 提交时间: 2023-09-18 15:12:05
'''
dp[i][j] 表示数组 board 中位置 (i, j) 的若干状态.
由于题目要求得到从右下角到左上角的得分最大值以及最大得分方案数
，因此 dp[i][j] 中需要存储两个状态：一个表示从右下角到位置 (i, j) 的得分最大值，
另一个表示从右下角到位置 (i, j) 的最大得分方案数。
如果从右下角无法到达位置 (i, j)（有两种情况，一是位置 (i, j) 是一个障碍，
二是由于障碍的存在，位置 (i, j) 无法到达），那么 dp[i][j] 中的第一个状态为 -1。
'''
class Solution:
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
n = len(board)
dp = [[[-1, 0]] * n for _ in range(n)]
dp[n - 1][n - 1] = [0, 1]
def update(x: int, y: int, u: int, v: int):
if u >= n or v >= n or dp[u][v][0] == -1:
return
if dp[u][v][0] > dp[x][y][0]:
dp[x][y] = dp[u][v][:]
elif dp[u][v][0] == dp[x][y][0]:
dp[x][y][1] += dp[u][v][1]
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
if not (i == n - 1 and j == n - 1) and board[i][j] != "X":
update(i, j, i + 1, j)
update(i, j, i, j + 1)
update(i, j, i + 1, j + 1)
if dp[i][j][0] != -1:
dp[i][j][0] += (0 if board[i][j] == "E" else ord(board[i][j]) - 48)
return [dp[0][0][0], dp[0][0][1] % (10**9 + 7)] if dp[0][0][0] != -1 else [0, 0]