C++刷leetcode（903. DI 序列的有效排列***）【动态规划】

糖逗

题目描述：

1. 我们给出 S，一个源于 {'D', 'I'} 的长度为 n 的字符串 。（这些字母代表 “减少” 和 “增加”。）
   
2. 有效排列 是对整数 {0, 1, ..., n} 的一个排列 P[0], P[1], ..., P[n]，使得对所有的 i：
   
3. 
   
4. 如果 S[i] == 'D'，那么 P[i] > P[i+1]，以及；
   
5. 如果 S[i] == 'I'，那么 P[i] < P[i+1]。
   
6. 有多少个有效排列？因为答案可能很大，所以请返回你的答案模 10^9 + 7.
   
7. 
   
8. &#160;
   
9. 
   
10. 示例：
    
11. 
    
12. 输入："DID"
    
13. 输出：5
    
14. 解释：
    
15. (0, 1, 2, 3) 的五个有效排列是：
    
16. (1, 0, 3, 2)
    
17. (2, 0, 3, 1)
    
18. (2, 1, 3, 0)
    
19. (3, 0, 2, 1)
    
20. (3, 1, 2, 0)
    
21. &#160;
    
22. 
    
23. 提示：
    
24. 
    
25. 1 <= S.length <= 200
    
26. S 仅由集合 {'D', 'I'}&#160;中的字符组成。
    
27. &#160;
    
28. 
    
29. 来源：力扣（LeetCode）
    
30. 链接：https://leetcode-cn.com/problems/valid-permutations-for-di-sequence
    
31. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     int mod = 1e9+7;
   
4. public:
   
5.     int numPermsDISequence(string S) {
   
6.         int n = S.size();
   
7.         vector<vector<int> > dp(n + 1, vector<int>(n + 1, 0));
   
8.         dp[0][0] = 1;
   
9.         for(int i = 1; i <= n; i++){
   
10.             for(int j = 0; j <= i; j++){
    
11.                 if(S[i-1] == 'D'){
    
12.                     for(int k = j; k < i; k++){
    
13.                         dp[i][j] += dp[i-1][k] ;
    
14.                         dp[i][j] = dp[i][j]%mod;
    
15.                     }
    
16.                 }else{
    
17.                     for(int k = 0; k < j; k++){
    
18.                         dp[i][j] += dp[i-1][k];
    
19.                         dp[i][j] = dp[i][j]%mod;
    
20.                     }
    
21.                 }
    
22.             }
    
23.         }
    
24.         int ans = 0;
    
25.         for(int j = 0; j <= n; j++){
    
26.             ans += dp[n][j];
    
27.             ans = ans % mod;
    
28.         }
    
29.         return ans;
    
30.     }
    
31. };

复制代码

参考链接：https://leetcode-cn.com/problems ... a-jie-fa-by-mo-mo-/

糖逗