题目描述
给你一个整数 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
算法
(动态规划) $O(n)$
- 设 $f(i, j)$ 表示组成前 $i$ 个字符最后以字符 $j$ 结尾的方案数。其中,$0 \le j \le 4$,代表 5 种字符。
- 接下来逐一分析 $f(i, 0)$ 可以从 $i-1$ 的哪些字符转移。
'a'
可以从'e'
,'i'
和'u'
转移,所以 $f(i, 0) = f(i - 1, 1) + f(i - 1, 2) + f(i - 1, 4)$。 - 其他转移可以按类似的方式写出,最终答案为 $\sum_{j = 0} ^ {4} f(n - 1, j)$。
时间复杂度
- 状态数为 $O(n)$,每次转移用常数时间,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要额外的数组存储状态。因为每个状态之和上一个状态有关,则可以只用常数的空间。
- 故总空间复杂度为 $O(n)$,但可以优化到 $O(1)$。
C++ 代码
class Solution {
public:
int countVowelPermutation(int n) {
vector<vector<int>> f(n, vector<int>(5));
const int mod = 1000000007;
int ans = 0;
for (int i = 0; i < 5; i++)
f[0][i] = 1;
for (int i = 1; i < n; i++) {
f[i][0] = ((f[i - 1][1] + f[i - 1][2]) % mod + f[i - 1][4]) % mod;
f[i][1] = (f[i - 1][0] + f[i - 1][2]) % mod;
f[i][2] = (f[i - 1][1] + f[i - 1][3]) % mod;
f[i][3] = f[i - 1][2];
f[i][4] = (f[i - 1][2] + f[i - 1][3]) % mod;
}
for (int i = 0; i < 5; i++)
ans = (ans + f[n - 1][i]) % mod;
return ans;
}
};
可以用enum使得代码更具可读性