C++刷LeetCode（1641. 统计字典序元音字符串的数目）【动态规划】

糖逗

题目描述：

1. 给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
   
2. 
   
3. 字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
   
4. 
   
5. 
   
6. 
   
7. 示例 1：
   
8. 
   
9. 输入：n = 1
   
10. 输出：5
    
11. 解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]
    
12. 示例 2：
    
13. 
    
14. 输入：n = 2
    
15. 输出：15
    
16. 解释：仅由元音组成的 15 个字典序字符串为
    
17. ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
    
18. 注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后
    
19. 示例 3：
    
20. 
    
21. 输入：n = 33
    
22. 输出：66045
    
23. 
    
24. 
    
25. 提示：
    
26. 
    
27. 1 <= n <= 50

复制代码

1. class Solution {
   
2. public:
   
3.     int countVowelStrings(int n) {
   
4.         //动态规划
   
5.         if(n == 1) return 5;
   
6.         //定义dp【i】【j】是以前i个（从0开始）为结尾的，且长度为j的字符串的个数
   
7.         int dp[5][n + 1];
   
8.         dp[0][1] = 1, dp[1][1] = 2, dp[2][1] = 3, dp[3][1] = 4, dp[4][1] = 5;
   
9.         for(int i = 0; i < 5; i++){
   
10.             for(int j = 2; j <= n; j++){
    
11.                 if(i == 0)dp[i][j] = dp[i][j-1];
    
12.                 else{
    
13.                     dp[i][j] = dp[i-1][j] + dp[i][j-1];//最后两个字符相同和不同两种情况
    
14.                 }
    
15.             }
    
16.         }
    
17.         return dp[4][n];
    
18.     }
    
19. };

复制代码

参考链接：https://leetcode-cn.com/problems ... n-mou-xian-de-me-w/

糖逗

动态规划类问题一直没有找到有效的解题方法