题目描述
给你一个整数 n
,请你帮忙统计一下我们可以按下述规则形成多少个长度为 n
的字符串:
- 字符串中的每个字符都应当是小写元音字母(
'a'
,'e'
,'i'
,'o'
,'u'
) - 每个元音
'a'
后面都只能跟着'e'
- 每个元音
'e'
后面只能跟着'a'
或者是'i'
- 每个元音
'i'
后面 不能 再跟着另一个'i'
- 每个元音
'o'
后面只能跟着'i'
或者是'u'
- 每个元音
'u'
后面只能跟着'a'
由于答案可能会很大,所以请你返回 模 10^9 + 7 之后的结果。
样例
输入:n = 1
输出:5
解释:所有可能的字符串分别是:"a", "e", "i" , "o" 和 "u"。
输入:n = 2
输出:10
解释:所有可能的字符串分别是:"ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。
输入:n = 5
输出:68
1 <= n <= 2 * 10^4
算法
(DP) $O(n)$
f[0]
代表af[1]
代表ef[2]
代表if[3]
代表of[4]
代表u-
f[i]
代表以对应字母结尾满足规则的长度 -
pre代表上一个长度状态的对应字母结尾满足规则的长度
f[0]
=pre[2]
+pre[1]
+pre[4]
;
f[1]
=pre[2]
+pre[0]
;
f[2]
=pre[1]
+pre[3]
;
f[3]
=pre[2]
;
f[4]
=pre[2]
+pre[3]
;
解释:
根据题意反过来推, a
的前面只能跟着i e u, e
的前面只能跟着i a, i
的前面只能跟着e u, o
的前面只能跟着i, u
的前面只能跟着i o
所以f[i]
当前长度为k的时候, 可以在k-1长度的字母后面添加上对应的字母(即pre[i]) 求出f[i]。每次只有上一个状态决定,所以可以使用滚动数组。
最后在统计以每个字母结尾长度为n的数目即为答案。
C++ 代码
const int MOD = 1e9+7;
class Solution {
// a e i o u
// 0 1 2 3 4
private:
long long f[5] = {1, 1, 1, 1, 1}; // f[i]代表以对应字母结尾满足规则的长度
public:
int countVowelPermutation(int n) {
long long pre[5] = {1, 1, 1, 1, 1}; // 因为使用滚动数组,保存f[i-1]的状态用于获取
for (int i = 2; i <= n; i++) {
f[0] = pre[2] + pre[1] + pre[4]; // a
f[1] = pre[2] + pre[0]; // e
f[2] = pre[1] + pre[3]; // i
f[3] = pre[2]; // o
f[4] = pre[2] + pre[3]; // u
for (int i = 0; i < 5; i++) pre[i] = f[i] % MOD;
}
long long res = 0;
for (const auto& x : f) {
res += x;
res %= MOD;
}
return res;
}
};