C ++中得分最高的路径数
我们必须找到两个数字的列表：第一个数字是我们可以收集的数字字符的最大和，第二个数字是我们可以用来获得最大和的此类路径的数量。对于答案，以10^9+7为模。如果没有路径，则返回[0，0]。
因此，如果输入类似于board=[“E12”，“1X1”，“21S”]，则输出将为[1,2]
为了解决这个问题，我们将遵循以下步骤-
n：=行数，m：=列数
定义一个nxmx2阶的3D数组
dp[n-1，m-1，0]=0，dp[n-1，m-1，1]=1
对于初始化i：=m-2，当i>=0时，更新（将i减1），执行-
dp[n-1，i，0]=b[n-1，i]-ASCII'0'+dp[n-1，i+1，0]
如果b[n-1，i]与'X'的ASCII相同，则-
dp[n-1，i，1]+=dp[n-1，i+1，1]
对于初始化i：=n-2，当i>=0时，更新（将i减1），执行-
dp[i，m-1，0]=b[i，m-1]-ASCII'0'+dp[i+1，m-1，0]
如果b[i，m-1]与'X'的ASCII相同，则-
dp[i，m-1，1]+=dp[i+1，m-1，1]
对于初始化i：=n-2，当i>=0时，更新（将i减1），执行-
如果b[i，j]与'X'的ASCII相同，则-
maxVal：={dp[i，j+1，0]，dp[i+1，j，0]，dp[i+1，j+1，0]}的最大值
如果maxVal等于0并且（b[i+1，j]不等于'S'的ASCII且b[i，j+1]不等于'S'的ASCII和b[i+1，j+1]不等于ASCII的“S”），则-
dp[i，j，0]：=dp[i，j，0]+maxVal
如果dp[i+1，j，0]与maxVal相同，则-
如果dp[i+1，j+1，0]与maxVal相同，则-
如果dp[i，j+1，0]与maxVal相同，则-
dp[i，j，1]：=dp[i，j，1]modm
dp[i，j，0]：=dp[i，j，0]modm
dp[i，j，0]：=（如果b[i，j]与'E'的ASCII相同，则为0，否则b[i，j]-'0'的ASCII）
dp[i，j，0]：=0
忽略以下部分，跳至下一个迭代
dp[i，j，1]：=dp[i，j，1]+dp[i+1，j，1]
dp[i，j，1]：=dp[i，j，1]+dp[i+1，j+1，1]
dp[i，j，1]：=dp[i，j，1]+dp[i，j+1，1]
对于初始化j：=m-2，当j>=0时，更新（将j减1），-
返回dp[0，0]
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
} cout << "]"<<endl;
}
typedef long long int lli;
const lli m = 1e9 + 7;
lli add(lli a, lli b){
return ((a % m) + (b % m) % m);
} class Solution {
public:
vector<int> pathsWithMaxScore(vector<string>& b) {
int n = b.size();
int m = b[0].size();
vector < vector < vector <int> > > dp(n, vector < vector
<int> >(m, vector <int> (2)));
dp[n - 1][m - 1][0] = 0;
dp[n - 1][m - 1][1] = 1;
for(int i = m - 2; i >= 0; i--){
if(b[n - 1][i] == 'X')break;
dp[n - 1][i][0] = b[n - 1][i] - '0' + dp[n - 1][i + 1]
[0];
dp[n - 1][i][1] += dp[n - 1][i + 1][1];
}
for(int i = n - 2; i >= 0; i--){
if(b[i][m - 1] == 'X')break;
dp[i][m - 1][0] = b[i][m - 1] - '0' + dp[i + 1][m - 1]
[0];
dp[i][m - 1][1] += dp[i + 1][m - 1][1];
}
for(int i = n - 2; i >= 0; i--){
for(int j = m - 2; j >= 0; j--){
if(b[i][j] == 'X')continue;
dp[i][j][0] = b[i][j] == 'E' ? 0 :b[i][j] - '0';
int maxVal = max({dp[i][j + 1][0], dp[i + 1][j][0],
dp[i + 1][j + 1][0]});
if(maxVal == 0 && (b[i+1][j] != 'S' && b[i][j + 1] !
= 'S' && b[i+1][j + 1] != 'S')){
dp[i][j][0] = 0;
continue;
}
dp[i][j][0] += maxVal;
if(dp[i + 1][j][0] == maxVal){
dp[i][j][1] += dp[i + 1][j][1];
}
if(dp[i + 1][j + 1][0] == maxVal){
dp[i][j][1] += dp[i + 1][j + 1][1];
}
if(dp[i][j + 1][0] == maxVal){
dp[i][j][1] += dp[i][j + 1][1];
}
dp[i][j][1] %= m;
dp[i][j][0] %= m;
}
}
return dp[0][0];
}
};
main(){
Solution ob;
vector<string> v = {"E12","1X1","21S"};
print_vector(ob.pathsWithMaxScore(v));
}输入项
{"E12","1X1","21S"}输出结果
[1, 2, ]