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]。
我们必须找到多少个有效排列？答案可能非常大，因此我们将使用mod10^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）modm
dp[i+1，j]=（dp[i+1，j]+curr）
对于初始化j：=0，curr：=0，当j<n-i时，更新（j增加1），-
curr：=（dp[i，j]+curr）modm
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