Leetcode 903

Leetcode 903

题目大意： 求符合DI字符串的序列的个数

代码：
class Solution {
public:
    int numPermsDISequence(string S) {
        int res =0, n = S.size(),M=1e9+7;
        vector<vector<int>> dp(n+1,vector<int>(n+1));
        dp[0][0] = 1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=i;j++){
                if(S[i-1]=='D'){
                    for(int k=j;k<=i-1;k++){
                        dp[i][j] = dp[i][j] + dp[i-1][k];
                        dp[i][j] %= M;
                    }
                }else{
                    for(int k =0;k<=j-1;k++ ){
                        dp[i][j] = dp[i][j] + dp[i-1][k];
                        dp[i][j] %=M;
                    }
                }
            }
        }
        for(int i=0;i<=n;i++){
            res = res + dp[n][i];
            res%=M;
        }
        return res;
    }
};