LeetCode 903: Valid Permutations for DI Sequence

发表于 | | 阅读次数:
字数统计: 639 | 阅读时长 ≈ 2

题目链接

https://leetcode.com/problems/valid-permutations-for-di-sequence/

题意

我们给出 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.

题目类型

动态规划

题目分析

又一道动态规划题，涉及到对这种特殊序列的理解。

将求方案的问题拆解一下，求i长度的序列由求i-1长度的序列转换而来。

设f[i][j]为序列{0,1,…,i}以j作为结尾的排列总数。

当前字母为’D’时，显然i-1位上只能够取j+1,j+2,…i-1.但是这样可能会有重复的情况(前面的序列也有j)，这种情况我们只需要把序列中大于等于j的数全部加1，则能既满足原有性质又不产生重复(这一点拿几个例子推一下就可以了)。这样j也是可以转移的，因此有$ f[i][j] = f[i-1][j] + f[i-1][j+2] + … + f[i-1][i-1] $

当前字母为’I’时，显然i-1位上只能够取0,1,…j-1.这时仍然会有重复情况，像上文一样解决即可。同时，f[i][0]必定为0，做一下特判即可，可以得到$ f[i][j] = f[i-1][0] + f[i-1][j+2] + … + f[i-1][j-1] $

连续求和很容易用部分和技术搞定，因此复杂度只有$N^{2}$.

关于全部加1举个例子，假如前面的序列是{0,2,3,4,1}，此时我们在后面加入3，把大于等于的部分加1，新序列为{0,2,4,5,1,3}，数列大小关系不会发生改变。

时间复杂度

$O(N ^ {2})$

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int numPermsDISequence(string S) {
        const int Mod = 1000000007;
        int i, j, n = S.size();
        int f[202][202], sf[202][202];
        memset(f, 0, sizeof(f));
        memset(sf, 0, sizeof(sf));
        f[0][0] = sf[0][0] = 1;
        for (i = 1; i <= n; i++) {
            for (j = 0; j <= i; j++) {
                if (S[i - 1] == 'I') {
                    if (j == 0)
                        continue;
                    f[i][j] = sf[i - 1][j - 1];
                }
                else
                    f[i][j] = (sf[i - 1][i - 1] - (j > 0 ? sf[i - 1][j - 1]: 0) + Mod) % Mod;
                sf[i][j] = ((j > 0 ? sf[i][j - 1]: 0) + f[i][j]) % Mod;
            }
        }
        return sf[n][n];
    }
};
0%