leetcode 903

问题

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:

1
2
3
4
5
6
7
8
9
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'}.

分析

思路1:

dp[i][j] 表示 “由 i+1 个数字组成且第 i+1 个数字（即序列中的最后一个数字）是剩余数字中（包括当前数字）中第 j+1 小的数字” 时的有效序列个数。比如 dp[0][0] 表示序列只有1个数字，且该数字是生育数字中最小的，那就只能是0，所以 dp[0][0] == 1。

状态转移方程：

1
2
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 )

S[i] == 'D' 表示下标为 i+1 的数要比下标为 i 的数小。也就是说第 i+2 个数要比第 i+1 个数小。则可以来确定 dp[i+1][j] 的值。dp[i+1][j] 表示第 i+2 个数是剩下没有选择的元素中（包括当前数字）第 j 小的。dp[i+1][j] 的值就决定于 dp[i][k] (k > j)。同理，当 S[i] == 'I' 时，表示下标为 i+1 的数要比下标为 i 的数大。dp[i+1][j] 的值就决定于 dp[i][k] (k <= j) ，注意这里可以取等号。当 k == j 时，在处理第 i+1 个数时，所取的数是第 j 小个，那么当其取走之后，在处理第 i+2 个数时，所取的当前剩余元素的第 j 小个时，所取的值也一定大于第 i+1 个数所取的值。

最终的答案在 dp[n][0]

思路2:

dp[i][j] 表示由范围 [0, i] 内的数字组成且最后一个数字为j的不同序列的个数。

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

https://www.cnblogs.com/grandyang/p/11094525.html

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    const int mod = 1e9+7;
    int numPermsDISequence(string S) {
        int n = S.size();
        vector<vector<long long>> dp(n+1, vector<long long>(n+1, 0));
        for (int j = 0; j <= n; ++j) dp[0][j] = 1;
        for (int i = 0; i < n; ++i) {
            if (S[i] == 'D') {
                for (long long j = n-1-i, tot = 0; j >= 0; --j) {
                    dp[i+1][j] = (tot = (tot + dp[i][j+1])%mod);
                }
            } else {  // S[i] == 'I'
                for (long long j = 0, tot = 0; j < n - i; ++j) {
                    dp[i+1][j] = (tot = (tot + dp[i][j])%mod);
                }
            }
        }
        return dp[n][0];
    }
};

代码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
25
class Solution {
public:
    const int mod = 1e9+7;
    int numPermsDISequence(string S) {
        int n = S.size();
        vector<vector<long long>> dp(n+1, vector<long long>(n+1, 0));
        dp[0][0] = 1;
        for (int i = 0; i < n; ++i) {
            if (S[i] == 'D') {
                for (long long j = i, tot = 0; j >= 0; --j) {
                    dp[i+1][j] = (tot = (tot + dp[i][j])%mod);
                }
            } else {  // S[i] == 'I'
                for (long long j = 1, tot = 0; j <= i+1; ++j) {
                    dp[i+1][j] = (tot = (tot + dp[i][j-1])%mod);
                }
            }
        }
        long long ans = 0;
        for (int j = 0; j <= n; ++j) {
            ans += dp[n][j];
        }
        return ans%mod;
    }
};