LeetCode: 903. Valid Permutations for DI Sequence

题目描述

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 <= S.length <= 200
S consists only of characters from the set {'D', 'I'}.

解题思路

见 Share my O(N^3) => O(N^2) C++ DP solution. Including the thoughts of improvement.

AC 代码

class Solution {
public:
    int numPermsDISequence(string S) {
        int N = S.length() + 1;
        int MOD = 1e9 + 7;
        // dp[i][j] means number of permutation whose length is i and end with at most j.
        int dp[202][202] = {};
        dp[1][1] = 1;
        for (int i = 2; i <= N; ++i) {
            // length is i
            for (int j = 1; j <= i; ++j) {
                // end with j
                if (S[i - 2] == 'D') {
                    // decrease to j
                    dp[i][j] = (dp[i][j-1] + (dp[i-1][i-1] - dp[i-1][j-1]) % MOD) % MOD;
                } else {
                    // increase to j
                    dp[i][j] = (dp[i][j-1] + (dp[i-1][j-1] - dp[i-1][0]) % MOD) % MOD;
                }
            }
        }
        return (dp[N][N] + MOD) % MOD;
    }
};