计数dp(基础)

1641. 统计字典序元音字符串的数目 - 力扣（LeetCode）

class Solution {
public:int countVowelStrings(int n) {vector<vector<int>>dp(55,vector<int>(5));for(int i=0;i<=4;i++){dp[1][i]=1;}for(int i=2;i<=n;i++){for(int j=0;j<=4;j++){dp[i][j]=0;for(int k=j;k<=4;k++){dp[i][j]+=dp[i-1][k];}}}int result=0;for(int j=0;j<=4;j++){result+=dp[n][j];}return result;}
};

定义一个dp[i][j]二维数组，i代表字符串的长度，j代表开头字母（0代表a,1代表e.......）。

初始化dp数组，字符串长度为1的组合种类每一个字母都唯一，其他dp数组初始化为0，可以由字符串长度为1的状态向后推。

状态转移方程：

                for(int k=j;k<=4;k++){dp[i][j]+=dp[i-1][k];}

因为每次字符串的长度加一后，组合种类的数量等于原来这个字母开头的种类累加上长度减一后从这个字母开始向后的每一个字母的种类数。