C ++中DI序列的有效排列

假设我们有一个字符串S。这是一组{'D'，'I'}中的字符串。（D表示“减少”，而我的意思是“增加”）

现在考虑一个有效的排列是整数{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]。

我们必须找到多少个有效排列？答案可能非常大，因此我们将使用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

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 对于初始化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）

• 对于初始化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]与“ I”相同，则-

• 除此以外

• 返回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