C++의 DI 시퀀스에 대한 유효한 순열

문자열 S가 있다고 가정합니다. 이것은 {'D', 'I'} 집합의 문자 문자열입니다. (D는 "감소"를 의미하고 I는 "증가"를 의미)

이제 유효한 순열이 모든 i에 대해 다음 규칙을 충족하도록 정수 {0 ~ n}의 순열 P[0], P[1], ..., P[n]이라고 가정합니다.

• S[i] =='D'인 경우 P[i]> P[i+1];

• 그렇지 않으면 S[i] =='I'일 때 P[i]

유효한 순열이 몇 개나 있는지 찾아야 합니까? 답변이 매우 클 수 있으므로 mod 10^9 + 7을 사용하여 반환합니다.

따라서 입력이 "IDD"와 같으면 출력은 3이 됩니다. 따라서 (0,3,2,1), (1,3,2,0), ( 2,3,1,0).

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=S

  의 크기

• (n + 1) x (n + 1) 크기의 2D 배열 dp 하나 정의

• 초기화 j :=0의 경우 j <=n일 때 업데이트(j를 1만큼 증가), −

  • dp[0, j] :=1

• initialize i :=0의 경우, i

  • S[i]가 'I'와 같으면 -

    • 초기화 j :=0, curr :=0, j

      • curr :=(dp[i, j] + curr) 모드 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) 모드 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