Hoán vị hợp lệ cho chuỗi DI trong C ++

Giả sử chúng ta có một chuỗi S. Đây là một chuỗi các ký tự từ tập {'D', 'I'}. (D có nghĩa là "giảm" và I có nghĩa là "tăng")

Bây giờ hãy coi một hoán vị hợp lệ là một hoán vị P [0], P [1], ..., P [n] của các số nguyên {0 đến n}, sao cho với mọi i, nó đáp ứng các quy tắc sau:

• Nếu S [i] =='D' thì P [i]> P [i + 1];

• Ngược lại khi S [i] =='I' thì P [i]

Ta phải tìm xem có bao nhiêu hoán vị hợp lệ? Câu trả lời có thể rất lớn, vì vậy chúng tôi sẽ quay lại bằng cách sử dụng mod 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như "IDD", thì đầu ra sẽ là 3, Vì vậy, sẽ có ba hoán vị khác nhau, chúng giống như (0,3,2,1), (1,3,2,0), ( 2,3,1,0).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của S

• Xác định một dp mảng 2D có kích thước (n + 1) x (n + 1)

• để khởi tạo j:=0, khi j <=n, cập nhật (tăng j lên 1), thực hiện -

  • dp [0, j]:=1

• để khởi tạo i:=0, khi i

  • nếu S [i] giống với 'I', thì -

    • để khởi tạo j:=0, curr:=0, khi j

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

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

  • nếu không thì

    • để khởi tạo j:=n - i - 1, curr:=0, khi j> =0, cập nhật (giảm j đi 1), làm -

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

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

• trả về dp [n, 0]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

"IDD"

Đầu ra

3