LeetCode#1641

LeetCode#1641统计字典序元音字符串的数目

题目链接
这是一道偏找规律(bushi的题，给出五个元音字母，然后给定n，问你按照字典序排序一共有多少种组合方式。如果是二维的话使用动态规划还是比较简单的，第一维表示以哪个字母为结尾，第二维表示当前字符串的长度。所以状态转移方程就出来了：

dp[0][n] = dp[0][n-1] //长度为n的以a为结尾的字符串，只能由长度n-1的结尾为a的字符串填一个a构成
dp[1][n] = dp[0][n-1]+dp[1][n-1] //长度为n的以e为结尾的字符串，只能由长度n-1的结尾为a e的字符串填一个e构成
dp[2][n] = dp[0][n-1]+dp[1][n-1]+dp[2][n-1] //长度为n的以i为结尾的字符串，只能由长度n-1的结尾为a e i的字符串填一个i构成
//下面的以此类推

因为这种写法太丑陋了，我就稍微进行一下假的压缩，dp[i][n]=dp[0][n]+dp[1][n]+…+dp[i-1][n]+dp[i][n]，再完善一下，代码就出来了：

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