1220. Count Vowels Permutation

题目信息

题号:

1220

难度:

Hard

主题:

动态规划、状态转移、计数

原题:

LeetCode 1220

重点:

字符串只使用五个元音,每个字符允许的后继集合固定;答案对 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
解释:没有相邻字符需要检查,五个元音各形成一个合法字符串。