题目描述 DI 序列的有效排列

我们给出 S，一个源于 {'D', 'I'} 的长度为 n 的字符串 。（这些字母代表 “减少” 和 “增加”。）
有效排列 是对整数 {0, 1, ..., 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.

示例

输入："DID"
输出：5
解释：
(0, 1, 2, 3) 的五个有效排列是：
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)

解题思路

代码

class Solution {
public:
    int numPermsDISequence(string S) {
        int M = pow(10, 9)+7;
        //第一维表示取到S的第几个字母，第二维表示取值，例如0，1，2，3,dp[i][3]结尾取3
        vector<vector<int>> dp(S.size()+1,vector<int>(S.size()+1,0));
        dp[0][0] = 1;
        for(int i = 0;i<S.size();i++){
            if(S[i] == 'I'){
                for(int j = 1;j<=i+1;j++){
                    dp[i+1][j] = (dp[i+1][j-1]+dp[i][j-1])%M;
                }
            }else{
                for(int j = i;j>=0;j--){
                    dp[i+1][j] = (dp[i+1][j+1]+dp[i][j])%M;
                }
            }
        }
        int res = 0;
        for(int i = 0;i<dp.size();i++){
            res=(res+dp[dp.size()-1][i])%M;
        }
        return res;
    }
};