# 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”.)

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'}`.

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

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

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

10 -> 10 -> 102
``````

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

201 -> 302 -> 3021
102 -> 203 -> 2031

102 -> 103 -> 1032
``````

``````1 0 0 0
1 0 0 0
0 1 1 0
2 2 1 0
``````

``````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[0][3] = 1  (3)
dp[0][2] = 1  (2)
dp[0][1] = 1  (1)
dp[0][0] = 1  (0)
``````

``````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][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[2][1] = 5 (3120, 2130, 3021, 2031, 1032)`

``````1 1 1 1
3 2 1 0
3 5 0 0
5 0 0 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 同步地址:

https://github.com/grandyang/leetcode/issues/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

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation