C++刷leetcode（903. DI 序列的有效排列***）【动态规划】
题目描述：我们给出 S，一个源于 {'D', 'I'} 的长度为 n 的字符串 。（这些字母代表 “减少” 和 “增加”。）
有效排列 是对整数 {0, 1, ..., n} 的一个排列 P, P, ..., P，使得对所有的 i：
如果 S == 'D'，那么 P > P，以及；
如果 S == 'I'，那么 P < P。
有多少个有效排列？因为答案可能很大，所以请返回你的答案模 10^9 + 7.
示例：
输入："DID"
输出：5
解释：
(0, 1, 2, 3) 的五个有效排列是：
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)
提示：
1 <= S.length <= 200
S 仅由集合 {'D', 'I'} 中的字符组成。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-permutations-for-di-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
private:
int mod = 1e9+7;
public:
int numPermsDISequence(string S) {
int n = S.size();
vector<vector<int> > dp(n + 1, vector<int>(n + 1, 0));
dp = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= i; j++){
if(S == 'D'){
for(int k = j; k < i; k++){
dp += dp ;
dp = dp%mod;
}
}else{
for(int k = 0; k < j; k++){
dp += dp;
dp = dp%mod;
}
}
}
}
int ans = 0;
for(int j = 0; j <= n; j++){
ans += dp;
ans = ans % mod;
}
return ans;
}
};
参考链接：https://leetcode-cn.com/problems/valid-permutations-for-di-sequence/solution/tu-jie-nong-qing-dong-tai-gui-hua-jie-fa-by-mo-mo-/ {:10_302:}
页:
[1]