题目
给你一个正方形字符数组 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[i][j]表示位置(i,j)的最大得分,则dp[i][j]=max(dp[i+1][j],dp[i][j+1],dp[i+1][j+1])。
则dp[0][0]就是答案。m为board的长度,n为每一个字符串的长度。dp[m-1][n-1]就是S的位置的最大得分。
而m-1行的状态,只能从dp[i][j+1]转移而来,n-1列的状态,只能从dp[i+1][j]转移而来。题目还要求最大
得分的路径数,对于dp[i+1][j],dp[i][j+1],dp[i+1][j+1],假设它们的路径数分别为2,2,3,dp[i+1][j]
为最大值,同时dp[i+1][j]=dp[i][j+1],则dp[i][j]的路径数为2+2种。用一个数组来表示最大得分和其路径数
dp[i][j][0]表示最大得分,dp[i][j][1]表示路径数。每次算出最大得分的时候,再判断一下是否有相同的最大得分
如果有,则加上。
代码
class Solution {
public:
int mod = 1000000007;
vector<int> pathsWithMaxScore(vector<string>& board) {
int m = board.size();
if(m == 0) {
return {0,0};
}
int n = board[0].size();
vector<vector<vector<int>>> dp(m,vector<vector<int>>(n,vector<int>(2)));
for(int i = m-1;i >= 0;i--) {
for(int j = n-1;j >= 0;j--) {
//S位置的得分为0,路径数为1
if (i == m-1 && j == n-1) {
dp[i][j] = {0,1};
}
else if (i == m-1) {//最后一行,只能从右边转移而来
if (board[i][j] != 'X' && (board[i][j+1] == 'S' || dp[i][j+1][0] != 0)) {
int result = (dp[i][j+1][0] + (board[i][j]-'0')) % mod;
dp[i][j] = {result,1};
}
else {
dp[i][j] = {0,0};
}
}
else if (j == n-1) {//最后一列,只能从下边转移而来
if (board[i][j] != 'X' && (board[i+1][j] == 'S' || dp[i+1][j][0] != 0)) {
int result = (dp[i+1][j][0] + (board[i][j]-'0')) % mod;
dp[i][j] = {result,1};
}
else {
dp[i][j] = {0,0};
}
}
else {
if (board[i][j] != 'X') {
//先算出最大得分
vector<vector<int>> tmp = {dp[i+1][j],dp[i+1][j+1],dp[i][j+1]};
int maxIndex = 0;
int max = dp[i+1][j][0];
for(int k = 1;k < 3;k++) {
if (tmp[k][0] > max) {
max = tmp[k][0];
maxIndex = k;
}
}
//然后找出相同的路径数
int path = tmp[maxIndex][1];
for(int k = 0;k < 3;k++) {
if (k != maxIndex && tmp[k][0] == max) {
path += tmp[k][1];
path %= mod;
}
}
//如果最大得分为0,并且路径数为0,则无路可通此处
if (max == 0 && path == 0) {
dp[i][j] = {0,0};
}
else {
if (board[i][j] == 'E') {
dp[i][j] = {max,path};
}
else {
int result = (max+(board[i][j]-'0'))%mod;
dp[i][j] = {result,path};
}
}
}
else {
dp[i][j] = {0,0};
}
}
}
}
return dp[0][0];
}
};