903. Valid Permutations for DI Sequence
for sequence valid DI Permutations
2023-09-11 14:22:45 时间
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'
, thenP[i] > P[i+1]
, and; - If
S[i] == 'I'
, thenP[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'}
.
Approach #1: DP.[C++]
class Solution { public: int numPermsDISequence(string S) { int n = S.length(), mod = 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]) % mod; } else { for (int j = n - i - 1, cur = 0; j >= 0; --j) dp[i+1][j] = cur = (cur + dp[i][j+1]) % mod; } } return dp[n][0]; } };
Analysis:
I feel this code is right, but I can't express why.
https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/168278/C%2B%2BJavaPython-DP-Solution-O(N2)
相关文章
- [Functional Programming ADT] Create a Redux Store for Use with a State ADT Based Reducer
- [io PWA] Great libraries and tools for great Progressive Web Apps
- [AWS] AWS Control Tower for multi accounts
- [Vue + TS] Watch for Changes in Vue Using the @Watch Decorator with TypeScript
- Centos 无法获取IP-- No suitable device found for this connection device lo not available because
- 【已解决】SQLException: Invalid value for getInt() - ‘田鹏‘
- v-for最后一项不显示
- `Warning: The default method for RunUMAP has changed from calling Python UMAP via reticulate to the
- Laravel [1045] 解决方法 Access denied for user 'homestead'@'localhost'
- 【文献学习】2 Power of Deep Learning for Channel Estimation and Signal Detection in OFDM
- FlexGantt 8.0 for java Crack