C++でDIシーケンスの有効な順列を数える方法

文字列 S を考えます。この文字列は集合 {'D', 'I'} に属する文字のみで構成されています。「D」は「減少（decreasing）」、「I」は「増加（increasing）」を意味します。

ここで、有効な順列とは、整数 {0 から n} の順列 P[0], P[1], ..., P[n] のうち、すべての i について次の規則を満たすものを指します。

• S[i] == 'D' の場合、P[i] > P[i+1] を満たす

• それ以外（S[i] == 'I' の場合）、P[i] < P[i+1] を満たす

私たちの課題は、そのような有効な順列が何通り存在するかを求めることです。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返します。

たとえば、入力が "IDD" の場合、出力は 3 になります。具体的には、(0,3,2,1)、(1,3,2,0)、(2,3,1,0) の3通りの異なる順列が存在します。

解法のアプローチ

この問題は動的計画法（DP）を用いて効率的に解くことができます。手順は以下の通りです。

• n := 文字列 S の長さとします

• (n + 1) × (n + 1) のサイズを持つ二次元配列 dp を定義します

• j := 0 として初期化し、j <= n の間 j を1ずつ増やしながら以下を実行します

  • dp[0][j] := 1

• i := 0 として初期化し、i < n の間 i を1ずつ増やしながら以下を実行します

  • S[i] が 'I' の場合

    • j := 0、curr := 0 として初期化し、j < n - i の間 j を1ずつ増やしながら以下を実行します

      • curr := (dp[i][j] + curr) mod m

      • dp[i + 1][j] = (dp[i + 1][j] + curr)

  • それ以外の場合（S[i] が 'D' の場合）

    • 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] を返します

このDPでは、dp[i][j] は「最初の i 文字の制約を処理した後、残りの数字の中で j 番目に小さい値を選んだ状態」に対応する順列の個数を表します。'I' の場合は累積和を左から右へ、'D' の場合は右から左へ計算することで、各遷移を O(1) で処理でき、全体の計算量は O(n²) になります。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

#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