1220. Count Vowels Permutation¶
题目信息¶
- 题号:
1220
- 难度:
Hard
- 主题:
动态规划、状态转移、计数
- 原题:
- 重点:
字符串只使用五个元音,每个字符允许的后继集合固定;答案对
10^9 + 7取模
题目重述¶
给定整数 n,统计长度为 n、只由 a、e、i、o、u 组成且满足以下相邻规则的字符串数量:a 后只能接 e;e 后只能接 a 或 i;i 后不能接 i;o 后只能接 i 或 u;u 后只能接 a。
返回合法字符串总数对 10^9 + 7 取模后的结果。
1 <= n <= 2 * 10^4。
自建示例¶
多轮状态转移累计所有合法字符串:
输入:n = 4
输出:35
解释:按每个末尾元音分类计数,长度为 4 时五类数量之和为 35。
长度为一时任意元音都合法:
输入:n = 1
输出:5
解释:没有相邻字符需要检查,五个元音各形成一个合法字符串。