C++で最大スコアを持つパスの数

2つの数値のリストを見つける必要があります。最初の数値は収集できる数字の最大合計であり、2番目の数値はその最大合計を取得するために取ることができるそのようなパスの数です。答えについては、10 ^ 9 + 7を法として返します。パスがない場合は、[0、0]を返します。

したがって、入力がboard =["E12"、 "1X1"、 "21S"]の場合、出力は[1,2]

これを解決するには、次の手順に従います-

• n：=行数、m：=列数

• 次数nxmx2の3D配列を1つ定義します

• dp [n-1、m-1、0] =0、dp [n-1、m-1、1] =1

• 初期化i：=m-2の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • b [n-1、i]が'X'のASCIIと同じである場合、-

    • dp [n-1、i、0] =b [n-1、i]-「0」のASCII + dp [n-1、i + 1、0]

  • dp [n-1、i、1] + =dp [n-1、i + 1、1]

• 初期化i：=n-2の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • b [i、m-1]が'X'のASCIIと同じである場合、-

    • dp [i、m-1、0] =b [i、m-1]-「0」のASCII + dp [i + 1、m-1、0]

  • dp [i、m-1、1] + =dp [i + 1、m-1、1]

• 初期化i：=n-2の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • 初期化j：=m-2の場合、j> =0の場合、更新（jを1つ減らす）、実行-

    • b [i、j]が'X'のASCIIと同じである場合、-

      • dp [i、j、0]：=（b [i、j]が'E'のASCIIと同じ場合は0、それ以外の場合はb [i、j]-'0'の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]は'S'のASCIIと等しくない）、次に-

      • dp [i、j、0]：=0

      • 次の部分を無視し、次の反復にスキップします

    • dp [i、j、0]：=dp [i、j、0] + maxVal

    • dp [i + 1、j、0]がmaxValと同じである場合、-

      • dp [i、j、1]：=dp [i、j、1] + dp [i + 1、j、1]

    • dp [i + 1、j + 1、0]がmaxValと同じ場合、-

      • dp [i、j、1]：=dp [i、j、1] + dp [i + 1、j + 1、1]

    • dp [i、j + 1、0]がmaxValと同じである場合、-

      • dp [i、j、1]：=dp [i、j、1] + dp [i、j + 1、1]

    • dp [i、j、1]：=dp [i、j、1] mod m

    • dp [i、j、0]：=dp [i、j、0] mod m

• 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, ]