1220. 统计元音字母序列的数目 #
- 标签:动态规划
- 难度:困难
题目大意 #
描述:给定一个整数 n
,我们可以按照以下规则生成长度为 n
的字符串:
- 字符串中的每个字符都应当是小写元音字母(
'a'
、'e'
、'i'
、'o'
、'u'
)。 - 每个元音
'a'
后面都只能跟着'e'
。 - 每个元音
'e'
后面只能跟着'a'
或者是'i'
。 - 每个元音
'i'
后面不能再跟着另一个'i'
。 - 每个元音
'o'
后面只能跟着'i'
或者是'u'
。 - 每个元音
'u'
后面只能跟着'a'
。
要求:统计一下我们可以按上述规则形成多少个长度为 n
的字符串。由于答案可能会很大,所以请返回模 $10^9 + 7$ 之后的结果。
说明:
- $1 \le n \le 2 * 10^4$。
示例:
- 示例 1:
|
|
解题思路 #
思路 1:动态规划 #
根据题目给定的字符串规则,我们可以将其整理一下:
- 元音字母
'a'
前面只能跟着'e'
、'i'
、'u'
。 - 元音字母
'e'
前面只能跟着'a'
、'i'
。 - 元音字母
'i'
前面只能跟着'e'
、'o'
。 - 元音字母
'o'
前面只能跟着'i'
。 - 元音字母
'u'
前面只能跟着'o'
、'i'
。
现在我们可以按照字符串的长度以及字符结尾进行阶段划分,并按照上述规则推导状态转移方程。
1. 划分阶段 #
按照字符串的结尾位置和结尾位置上的字符进行阶段划分。
2. 定义状态 #
定义状态 dp[i][j]
表示为:长度为 i
并且以字符 j
结尾的字符串数量。这里 $j = 0, 1, 2, 3, 4$ 分别代表元音字母 'a'
、'e'
、'i'
、'o'
、'u'
。
3. 状态转移方程 #
通过上面的字符规则,可以得到状态转移方程为:
$\begin{cases} dp[i][0] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4] \cr dp[i][1] = dp[i - 1][0] + dp[i - 1][2] \cr dp[i][2] = dp[i - 1][1] + dp[i - 1][3] \cr dp[i][3] = dp[i - 1][2] \cr dp[i][4] = dp[i - 1][2] + dp[i - 1][3] \end{cases}$
4. 初始条件 #
- 长度为
1
并且以字符j
结尾的字符串数量为1
,即dp[1][j] = 1
。
5. 最终结果 #
根据我们之前定义的状态,dp[i]
表示为:长度为 i
并且以字符 j
结尾的字符串数量。则将 dp[n]
行所有列相加,就是长度为 n
的字符串数量。
思路 1:动态规划代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。