C++でのDIシーケンスの有効な順列

文字列Sがあるとします。これは、セット{'D'、'I'}の文字列です。 （Dは「減少」を意味し、Iは「増加」を意味します）

ここで、有効な順列が{0からn}の整数の順列P [0]、P [1]、...、P [n]であると考えてください。これにより、すべてのiについて、次のルールが満たされます。

• S [i] =='D'の場合、P [i]> P [i + 1];

• それ以外の場合、S [i] =='I'の場合、P [i]

有効な順列がいくつあるかを見つける必要がありますか？答えは非常に大きい可能性があるため、mod 10 ^ 9+7を使用して戻ります。

したがって、入力が「IDD」のような場合、出力は3になります。したがって、3つの異なる順列があり、これらは（0,3,2,1）、（1,3,2,0）、（ 2,3,1,0）。

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

• n：=Sのサイズ

• サイズ（n + 1）x（n + 1）の2D配列dpを1つ定義します

• 初期化j：=0の場合、j <=nの場合、更新（jを1増やします）、実行-

  • dp [0、j]：=1

• 初期化i：=0の場合、i

  • S[i]が'I'と同じ場合、-

    • 初期化j：=0、curr：=0の場合、j

      • curr：=（dp [i、j] + curr）mod m

      • dp [i + 1、j] =（dp [i + 1、j] + curr）

  • それ以外の場合

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

      • curr：=（dp [i、j + 1] + curr）mod m

      • dp [i + 1、j] =（dp [i + 1、j] + curr）

• dp [n、0]

  を返します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
   public:
   int numPermsDISequence(string S) {
      int n = S.size();
      vector<vector<int>> dp(n + 1, vector<int>(n + 1));
      for (int j = 0; j <= n; j++)
      dp[0][j] = 1;
      for (int i = 0; i < n; i++) {
         if (S[i] == 'I') {
            for (int j = 0, curr = 0; j < n - i; j++) {
               curr = (dp[i][j] + curr) % m;
               dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
            }
         } else {
            for (int j = n - i - 1, curr = 0; j >= 0; j--) {
               curr = (dp[i][j + 1] + curr) % m;
               dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
            }
         }
      }
      return dp[n][0];
   }
};
main(){
   Solution ob;
   cout << (ob.numPermsDISequence("IDD"));
}

入力

"IDD"

出力

3