[LeetCode] 903. Valid Permutations for DI Sequence

[grandyang]

We are given S, a length n string of characters from the set {'D', 'I'}. (These letters stand for "decreasing" and "increasing".)

A  valid permutation  is a permutation P[0], P[1], ..., P[n] of integers {0, 1, ..., n}, such that for all i:

• If S[i] == 'D', then P[i] > P[i+1], and;
• If S[i] == 'I', then P[i] < P[i+1].

How many valid permutations are there?  Since the answer may be large, return your answer modulo 10^9 + 7.

Example 1:

Input: "DID"
Output: 5
Explanation:
The 5 valid permutations of (0, 1, 2, 3) are:
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)

Note:

1. 1 <= S.length <= 200
2. S consists only of characters from the set {'D', 'I'}.

这道题给了我们一个长度为n的字符串S，里面只有两个字母D和I，分别表示下降 Decrease 和上升 Increase，意思是对于 [0, n] 内所有数字的排序，必须满足S的模式，比如题目中给的例子 S="DID"，就表示序列需要先降，再升，再降，于是就有那5种情况。题目中提示了结果可能会是一个超大数，让我们对 1e9+7 取余，经验丰富的刷题老司机看到这里就知道肯定不能递归遍历所有情况，编译器估计都不允许，这里动态规划 Dynamic Programming 就是不二之选，但是这道题正确的动态规划解法其实是比较难想出来的，因为存在着关键的隐藏信息 Hidden Information，若不能正确的挖掘出来（山东布鲁斯特挖掘机专业了解一下？），是不太容易解出来的。首先来定义我们的 DP 数组吧，这里大家的第一直觉可能是想着就用一个一维数组 dp，其中 dp[i] 表示范围在 [0, i] 内的字符串S的子串能有的不同序列的个数。这样定义的话，就无法写出状态转移方程，像之前说的，我们忽略了很关键的隐藏信息。先来想，序列是升是降到底跟什么关系最大，答案是最后一个数字，比如我们现在有一个数字3，当前的模式是D，说明需要下降，所以可能的数字就是 0，1，2，但如果当前的数字是1，那么还要下降的话，那么貌似就只能加0了？其实也不一定，因为这道题说了只需要保证升降模式正确就行了，数字之间的顺序关系其实并不重要，举个例子来说吧，假如我们现在已经有了一个 "DID" 模式的序列 1032，假如我们还想加一个D，变成 "DIDD"，该怎么加数字呢？多了一个模式符，就多了一个数字4，显然直接加4是不行的，实际是可以在末尾加2的，但是要先把原序列中大于等于2的数字都先加1，即 1032 -> 1043，然后再加2，变成 10432，就是 "DIDD" 了。虽然我们改变了序列的数字顺序，但是升降模式还是保持不变的。同理，也是可以加1的，1032 -> 2043 -> 20431，也是可以加0的，1032 -> 2143 -> 21430。但是无法加3和4，因为 1032 最后一个数字2很很重要，所有小于等于2的数字，都可以加在后面，从而形成降序。那么反过来也是一样，若要加个升序，比如变成 "DIDI"，猜也猜的出来，后面要加大于2的数字，然后把所有大于等于这个数字的地方都减1，比如加上3，1032 -> 1042 -> 10423，再比如加上4，1032 -> 1032 -> 10324。

通过上面的分析，我们知道了最后一个位置的数字的大小非常的重要，不管是要新加升序还是降序，最后的数字的大小直接决定了能形成多少个不同的序列，这个就是本题的隐藏信息，所以我们在定义 dp 数组的时候必须要把最后一个数字考虑进去，这样就需要一个二维的 dp 数组，其中 dp[i][j] 表示由范围 [0, i] 内的数字组成且最后一个数字为j的不同序列的个数。就拿题目中的例子来说吧，由数字 [0, 1, 2, 3] 组成 "DID" 模式的序列，首先 dp[0][0] 是要初始化为1，如下所示（括号里是实际的序列）：

dp[0][0] = 1 (0)

然后需要加第二个数字，由于需要降序，那么根据之前的分析，加的数字不能大于最后一个数字0，则只能加0，如下所示：

加0:  ( dp[1][0] = 1 )
0 -> 1 -> 10

然后需要加第三个数字，由于需要升序，那么根据之前的分析，加的数字不能小于最后一个数字0，那么实际上可以加的数字有 1，2，如下所示：

加1:  ( dp[2][1] = 1 )
10 -> 20 -> 201

加2:  ( dp[2][2] = 1 )
10 -> 10 -> 102

然后需要加第四个数字，由于需要降序，那么根据之前的分析，加的数字不能大于最后一个数字，上一轮的最后一个数字有1或2，那么实际上可以加的数字有 0，1，2，如下所示：

加0:  ( dp[3][0] = 2 )
201 -> 312 -> 3120
102 -> 213 -> 2130

加1:  ( dp[3][1] = 2 )
201 -> 302 -> 3021
102 -> 203 -> 2031

加2:  ( dp[3][2] = 1 )
102 -> 103 -> 1032

这种方法算出的 dp 数组为：

1 0 0 0 
1 0 0 0 
0 1 1 0 
2 2 1 0 

最后把 dp 数组的最后一行加起来 2+2+1 = 5 就是最终的结果，分析到这里，其实状态转移方程已经不难得到了，根据前面的分析，当是降序时，下一个数字不小于当前最后一个数字，反之是升序时，下一个数字小于当前最后一个数字，所以可以写出状态转移方程如下所示：

if (S[i-1] == 'D')    dp[i][j] += dp[i-1][k]    ( j <= k <= i-1 )
else                  dp[i][j] += dp[i-1][k]    ( 0 <= k < j )

解法一：

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]) % M;
                    } 
                } else {
                    for (int k = 0; k <= j - 1; ++k) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % M;
                    }
                }
            }
        }
        for (int i = 0; i <= n; ++i) {
            res = (res + dp[n][i]) % M;
        }
        return res;
    }
};

我们还可以换一种形式 DP 解法，这里的 dp 数组在定义上跟之前的略有区别，还是用一个二维数组，这里的 dp[i][j] 表示由 i+1 个数字组成且第 i+1 个数字（即序列中的最后一个数字）是剩余数字中（包括当前数字）中第 j+1 小的数字。比如 dp[0][0]，表示序列只有1个数字，且该数字是剩余数字中最小的，那就只能是0。再比如，dp[1][2] 表示该序列有两个数字，且第二个数字是剩余数字中第三小的，那么序列只能是 32，因为剩余数字为 0，1，2（包括最后一个数字），这里2就是第三小的。有些情况序列不唯一，比如 dp[1][1] 表示该序列有两个数字，且第二个数字是剩余数字中第二小的，此时的序列就有 31（1是 0，1，2 中第二小的）和 21（1是 0，1，3 中第二小的）两种情况。搞清楚了 dp 的定义之后，再来推导状态转移方程吧，对于 dp[0][j] 的情况，十分好判断，因为只有一个数字，并不存在升序降序的问题，所以 dp[0][j] 可以都初始化为1，如下所示（括号里是实际的序列）：

dp[0][3] = 1  (3)
dp[0][2] = 1  (2)
dp[0][1] = 1  (1)
dp[0][0] = 1  (0)

然后需要加第二个数字，由于需要降序，那么根据之前的分析，新加的数字不可能是第四小的，所以不可能出现 dp[1][3] 为正数，因为这表示有两个数字，且第二个数字是剩余数字中的第四小，总共就四个数字，第四小的数字就是最大数字，由于是降序，所以第二个数字要小于第一个数字，这里就矛盾了，所以 dp[1][3] 一定为0，而其余的确实可以从上一层递推过来，具体来说，对于 dp[1][j]，需要累加 dp[0][k] ( j < k <= n-1 )：

dp[1][2] = dp[0][3] = 1  (32)
dp[1][1] = dp[0][3] + dp[0][2] = 2  (31, 21)
dp[1][0] = dp[0][3] + dp[0][2] + dp[0][1] = 3  (30, 20, 10)

然后需要加第三个数字，由于需要升序，那么根据之前的分析，此时已经有两个数字了，新加的第三个数字只可能是剩余数字的第一小和第二小，即只有 dp[2][0] 和 dp[2][1] 会有值，跟上面相似，其也是由上一层累加而来，对于 dp[2][j]，需要累加 dp[1][k] ( 0 <= k <= j ):

dp[2][1] = dp[1][1] + dp[1][0] = 5  (312, 213, 302, 203, 103)
dp[2][0] = dp[1][0] = 3  (301, 201, 102)

最后再加第四个数字，由于需要降序，那么根据之前的分析，此时已经有三个数字了，新加的第四个数字只可能是剩余数字的第一小，即只有 dp[3][0] 会有值，跟上面相似，其也是由上一层累加而来，对于 dp[3][j]，需要累加 dp[2][k] ( j< k <= n-1 )，这里有值的只有 dp[2][1]：

dp[3][0] = dp[2][1] = 5 (3120, 2130, 3021, 2031, 1032)

这种方法算出的 dp 数组为：

1 1 1 1 
3 2 1 0 
3 5 0 0 
5 0 0 0 

这种方法算出的最终结果一定是保存在 dp[n][0] 中的，分析到这里，其实状态转移方程已经不难得到了，如下所示：

if (S[i] == 'D')    dp[i+1][j] = sum(dp[i][k])    ( j < k <= n-1 )
else                dp[i+1][j] = sum(dp[i][k])    ( 0 <= k <= j )

解法二：

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

Github 同步地址:

#903

参考资料：

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

https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/168278/C%2B%2BJavaPython-DP-Solution-O(N2)

https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/196939/Easy-to-understand-solution-with-detailed-explanation

https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/168612/Top-down-with-Memo-greater-Bottom-up-DP-greater-N3-DP-greater-N2-DP-greater-O(N)-space

LeetCode All in One 题目讲解汇总(持续更新中...)