上海市建设工程信息报送网站,网站建设分金手指专业五,弥勒网站开发,同服务器网站查询工具题目链接 Leetcode.1220 统计元音字母序列的数目 Rating #xff1a; 1730 题目描述
给你一个整数 n#xff0c;请你帮忙统计一下我们可以按下述规则形成多少个长度为 n的字符串#xff1a;
字符串中的每个字符都应当是小写元音字母#xff08;a, e, i, o, u#xff09;…题目链接 Leetcode.1220 统计元音字母序列的数目 Rating 1730 题目描述
给你一个整数 n请你帮忙统计一下我们可以按下述规则形成多少个长度为 n的字符串
字符串中的每个字符都应当是小写元音字母a, e, i, o, u每个元音 a后面都 只能 跟着 e每个元音 e后面 只能 跟着 a或者是 i每个元音 i后面 不能 再跟着另一个 i每个元音 o后面 只能 跟着 i或者是 u每个元音 u后面 只能 跟着 a
由于答案可能会很大所以请你返回 模 10^9 7之后的结果。
示例 1 输入n 1 输出5 解释所有可能的字符串分别是“a”, “e”, “i” , “o” 和 “u”。 示例 2 输入n 2 输出10 解释所有可能的字符串分别是“ae”, “ea”, “ei”, “ia”, “ie”, “io”, “iu”, “oi”, “ou” 和 “ua”。 示例 3 输入n 5 输出68 提示
1n2∗1041 n 2 * 10^41n2∗104
分析线性dp
按照题目的要求合法的组合如下
结尾是 a的ea , ua , ia结尾是 e的ae , ie结尾是 i的ei , oi结尾是 o的io结尾是 u的·iu , ou
我们定义 f(i,j)f(i,j)f(i,j) 为第 j个字符为 a , e , i , o , u的方案数f(1,j)f(1,j)f(1,j) 就是第 j个字符为 a的方案数。
按照定义答案为 ans(f(1,n)f(2,n)f(3,n)f(4,n)f(5,n))modMODans (f(1,n)f(2,n)f(3,n)f(4,n) f(5,n)) mod MODans(f(1,n)f(2,n)f(3,n)f(4,n)f(5,n))modMOD
时间复杂度 O(n)O(n)O(n)
C代码
const int MOD 1e9 7;
using LL long long;
class Solution {
public:int countVowelPermutation(int n) {LL f[6][n1];memset(f,0,sizeof f);for(int i 1;i 5;i) f[i][1] 1;for(int i 2;i n;i){//ea , ia , uaf[1][i] (f[2][i-1] f[3][i-1] f[5][i-1]) % MOD;//ae , ief[2][i] (f[1][i-1] f[3][i-1]) % MOD;//ei , oif[3][i] (f[2][i-1] f[4][i-1]) % MOD;//iof[4][i] (f[3][i-1]) % MOD;//iu , ouf[5][i] (f[3][i-1] f[4][i-1]) % MOD;}LL ans 0;for(int i 1;i 5;i) ans (ans f[i][n]) % MOD;return ans;}
};
Java代码
class Solution {private final int MOD 1000_000_007;public int countVowelPermutation(int n) {long[][] f new long[6][n 1];for(int i 1;i 5;i) f[i][1] 1;//1-a 2-e 3-i 4-o 5-ufor(int i 2;i n;i){//ea , ia , uaf[1][i] (f[2][i-1] f[3][i-1] f[5][i-1]) % MOD;//ae , ief[2][i] (f[1][i-1] f[3][i-1]) % MOD;//ei , oif[3][i] (f[2][i-1] f[4][i-1]) % MOD;//iof[4][i] (f[3][i-1]) % MOD;//iu , ouf[5][i] (f[3][i-1] f[4][i-1]) % MOD;}long ans 0;for(int i 1;i 5;i) ans (ans f[i][n]) % MOD;return (int)ans;}
}
