给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：
- 字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'） - 每个元音 'a' 后面都只能跟着 'e' - 每个元音 'e' 后面只能跟着 'a' 或者是 'i' - 每个元音 'i' 后面 不能 再跟着另一个 'i' - 每个元音 'o' 后面只能跟着 'i' 或者是 'u' - 每个元音 'u' 后面只能跟着 'a'由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。
示例 1： 输入：n = 1 输出：5 解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。 示例 2： 输入：n = 2 输出：10 解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。 示例 3： 输入：n = 5 输出：68 提示： 1 <= n <= 2 * 10^4来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-vowels-permutation 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
类似题目： LeetCode 576. 出界的路径数（动态规划） LeetCode 688. “马”在棋盘上的概率（DP） LeetCode 935. 骑士拨号器（动态规划）
dp[k][0-4] 表示长度为 k 时，字母为 0 - 4 表示 aeiou 时的方案数 class Solution { public: int countVowelPermutation(int n) { int mod = 1e9+7; vector<vector<long long>> dp(n+1, vector<long long>(5, 0)); dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1; // a 0 e 1 i 2 o 3 u 4 //e,i,u --> a 上一个尾部字母 --》 下一个字母 //a, i --> e //e o --> i //i -- > o //i o --> u for(int k = 2; k <= n; ++k) { dp[k][0] = (dp[k-1][1]+dp[k-1][2]+dp[k-1][4])%mod; dp[k][1] = (dp[k-1][0]+dp[k-1][2])%mod; dp[k][2] = (dp[k-1][1]+dp[k-1][3])%mod; dp[k][3] = (dp[k-1][2])%mod; dp[k][4] = (dp[k-1][2]+dp[k-1][3])%mod; } int ans = 0; for(int i = 0; i < 5; i++) ans = (ans+dp[n][i])%mod; return ans; } };116 ms 27 MB
我的博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
