DI 序列的有效排列Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给定一个长度为 n 的字符串 s ，其中 s[i] 是:

“D” 意味着减少，或者
“I” 意味着增加

有效排列是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i：

如果 s[i] == 'D'，那么 perm[i] > perm[i+1]，以及；
如果 s[i] == 'I'，那么 perm[i] < perm[i+1]。

返回有效排列 perm的数量。因为答案可能很大，所以请返回你的答案对 109 + 7 取余。

示例 1：

输入：s = "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)

示例 2:

输入: s = "D"
输出: 1

提示:

n == s.length
1 <= n <= 200
s[i] 不是 'I' 就是 'D'

# 思路

# 解法


class Solution {
    public int numPermsDISequence(String S) {
        int n=S.length();
        int[][] dp=new int[n+1][n+1];
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=i;j++){
                if(S.charAt(i-1)=='D'){
                    for(int k=j;k<i;k++){
                        dp[i][j]=(dp[i][j]+dp[i-1][k])%1000000007;
                    }
                }
                else{
                    for(int k=0;k<j;k++){
                        dp[i][j]=(dp[i][j]+dp[i-1][k])%1000000007;
                    }
                }
            }
        }
        int res=0;
        for(int i=0;i<=n;i++){
            res=(res+dp[n][i])%1000000007;
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 总结

分析出几种情况，然后分别对各个情况实现