题目描述

给定 S，一个长度为 n 的字符串，字符来自 {'D', 'I'}。（这些字母表示“上升”或“下降”。）

一个合法的排列是整数 {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
解释：
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)

注意

• 1 <= S.length <= 200
• S 仅包含集合 {'D', 'I'} 的字母。

算法

(动态规划) $O(n^3)$

1. 区间动态规划，令 $f(i,j)$ 表示 $j - i + 1$ 个数的排列，满足区间 $S(i, j - 1)$ 的方案数。
2. 我们每次枚举最大数字的位置，其中可以放在区间开头，放在区间末尾，或者放在区间中某个位置。
3. 放在区间开头时，若 S(i) == 'D'，则我们转移 $f(i,j) = f(i, j) + f(i + 1, j)$；
4. 放在区间末尾时，若 S(j - 1) == 'I'，则我们转移 $f(i,j) = f(i, j) + f(i, j - 1)$；
5. 否则，枚举位置 $k \in [i+1, j-1]$，将区间分为两部分，若S(k - 1) == 'I' 并且 S(k) == 'D'，则根据乘法原理和组合数计算，转移 $f(i,j) = f(i, j) + C(len - 1, k - i) * f(i,k - 1) * f(k + 1, j)$，其中 $C$ 为组合数，这里代表从 $len - 1$ 个数中选择 $k-i$ 个数的方案数。
6. 初始化 $f(i, i)=1$；最后答案为 $f(1, n)$。以上脚标均是从 $1$ 开始，$n$ 是题目中的 $n+1$。

时间复杂度

• 状态数为 $O(n^2)$，转移数为 $O(n)$，故总时间复杂度为 $O(n^3)$。

C++ 代码

class Solution {
public:
    #define LL long long
    int numPermsDISequence(string S) {
        const int mod = 1000000007;
        S = " " + S;
        int n = S.length();
        vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));
        vector<vector<int>> C(n + 1, vector<int>(n + 1));

        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++)
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }

        for (int i = 1; i <= n; i++)
            f[i][i] = 1;

        for (int len = 2; len <= n; len++)
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;

                if (S[i] == 'D')
                    f[i][j] = (f[i][j] + f[i + 1][j]) % mod;

                if (S[j - 1] == 'I')
                    f[i][j] = (f[i][j] + f[i][j - 1]) % mod;

                for (int k = i + 1; k <= j - 1; k++)
                    if (S[k - 1] == 'I' && S[k] == 'D')
                        f[i][j] = (f[i][j] + (LL)(C[len - 1][k - i]) * f[i][k - 1] % mod * f[k + 1][j] % mod) % mod;

            }

        return f[1][n];
    }
};