假设我们有一个方形的字符板。我们可以从右下角标有“ S”的方框开始在板上移动。现在我们需要到达标记有字符“ E”的左上角正方形。其他正方形用从1到9的数字字符或障碍物“ X”标记。一举一动,只有在没有障碍物的情况下,我们才能向上,向左或向左上走。
我们必须找到两个数字的列表:第一个数字是我们可以收集的数字字符的最大和,第二个数字是我们可以用来获得最大和的此类路径的数量。对于答案,以10 ^ 9 + 7为模。如果没有路径,则返回[0,0]。
因此,如果输入类似于board = [“ E12”,“ 1X1”,“ 21S”],则输出将为[1,2]
为了解决这个问题,我们将遵循以下步骤-
n:=行数,m:=列数
定义一个nxmx 2阶的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] mod m
dp [i,j,0]:= dp [i,j,0] mod m
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, ]