动态规划
题目描述
给你一个整数 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
提示:
解法
方法一:动态规划
根据题目描述,我们先列出每个元音字母的后一个字母:
a [e]
e [a|i]
i [a|e|o|u]
o [i|u]
u [a]
那么我们可以推出每个元音字母的前一个字母:
[e|i|u] a
[a|i] e
[e|o] i
[i] o
[i|o] u
我们定义 $f[i]$ 表示当前长度以第 $i$ 个元音字母结尾的字符串的个数,如果长度为 $1$,那么 $f[i]=1$。
当长度大于 $1$ 时,我们定义 $g[i]$ 表示当前长度以第 $i$ 个元音字母结尾的字符串的个数,那么 $g[i]$ 可以由 $f$ 转移而来,即:
$$
g[i]=
\begin{cases}
f[1]+f[2]+f[4] & i=0 \
f[0]+f[2] & i=1 \
f[1]+f[3] & i=2 \
f[2] & i=3 \
f[2]+f[3] & i=4
\end{cases}
$$
最终答案为 $\sum_{i=0}^{4}f[i]$。注意由于答案可能会很大,所以需要对 $10^9+7$ 取模。
时间复杂度 $O(n)$,空间复杂度 $O(C)$。其中 $n$ 是字符串的长度,而 $C$ 是元音字母的个数。本题中 $C=5$。
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def countVowelPermutation ( self , n : int ) -> int :
f = [ 1 ] * 5
mod = 10 ** 9 + 7
for _ in range ( n - 1 ):
g = [ 0 ] * 5
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ]) % mod
g [ 1 ] = ( f [ 0 ] + f [ 2 ]) % mod
g [ 2 ] = ( f [ 1 ] + f [ 3 ]) % mod
g [ 3 ] = f [ 2 ]
g [ 4 ] = ( f [ 2 ] + f [ 3 ]) % mod
f = g
return sum ( f ) % mod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public int countVowelPermutation ( int n ) {
long [] f = new long [ 5 ] ;
Arrays . fill ( f , 1 );
final int mod = ( int ) 1e9 + 7 ;
for ( int i = 1 ; i < n ; ++ i ) {
long [] g = new long [ 5 ] ;
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ] ) % mod ;
g [ 1 ] = ( f [ 0 ] + f [ 2 ] ) % mod ;
g [ 2 ] = ( f [ 1 ] + f [ 3 ] ) % mod ;
g [ 3 ] = f [ 2 ] ;
g [ 4 ] = ( f [ 2 ] + f [ 3 ] ) % mod ;
f = g ;
}
long ans = 0 ;
for ( long x : f ) {
ans = ( ans + x ) % mod ;
}
return ( int ) ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public :
int countVowelPermutation ( int n ) {
using ll = long long ;
vector < ll > f ( 5 , 1 );
const int mod = 1e9 + 7 ;
for ( int i = 1 ; i < n ; ++ i ) {
vector < ll > g ( 5 );
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ]) % mod ;
g [ 1 ] = ( f [ 0 ] + f [ 2 ]) % mod ;
g [ 2 ] = ( f [ 1 ] + f [ 3 ]) % mod ;
g [ 3 ] = f [ 2 ];
g [ 4 ] = ( f [ 2 ] + f [ 3 ]) % mod ;
f = move ( g );
}
return accumulate ( f . begin (), f . end (), 0L L ) % mod ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 func countVowelPermutation ( n int ) ( ans int ) {
const mod int = 1e9 + 7
f := make ([] int , 5 )
for i := range f {
f [ i ] = 1
}
for i := 1 ; i < n ; i ++ {
g := make ([] int , 5 )
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ]) % mod
g [ 1 ] = ( f [ 0 ] + f [ 2 ]) % mod
g [ 2 ] = ( f [ 1 ] + f [ 3 ]) % mod
g [ 3 ] = f [ 2 ] % mod
g [ 4 ] = ( f [ 2 ] + f [ 3 ]) % mod
f = g
}
for _ , x := range f {
ans = ( ans + x ) % mod
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 function countVowelPermutation ( n : number ) : number {
const f : number [] = Array ( 5 ). fill ( 1 );
const mod = 1e9 + 7 ;
for ( let i = 1 ; i < n ; ++ i ) {
const g : number [] = Array ( 5 ). fill ( 0 );
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ]) % mod ;
g [ 1 ] = ( f [ 0 ] + f [ 2 ]) % mod ;
g [ 2 ] = ( f [ 1 ] + f [ 3 ]) % mod ;
g [ 3 ] = f [ 2 ];
g [ 4 ] = ( f [ 2 ] + f [ 3 ]) % mod ;
f . splice ( 0 , 5 , ... g );
}
return f . reduce (( a , b ) => ( a + b ) % mod );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 /**
* @param {number} n
* @return {number}
*/
var countVowelPermutation = function ( n ) {
const mod = 1e9 + 7 ;
const f = Array ( 5 ). fill ( 1 );
for ( let i = 1 ; i < n ; ++ i ) {
const g = Array ( 5 ). fill ( 0 );
g [ 0 ] = ( f [ 1 ] + f [ 2 ] + f [ 4 ]) % mod ;
g [ 1 ] = ( f [ 0 ] + f [ 2 ]) % mod ;
g [ 2 ] = ( f [ 1 ] + f [ 3 ]) % mod ;
g [ 3 ] = f [ 2 ];
g [ 4 ] = ( f [ 2 ] + f [ 3 ]) % mod ;
f . splice ( 0 , 5 , ... g );
}
return f . reduce (( a , b ) => ( a + b ) % mod );
};
方法二:矩阵快速幂加速递推
时间复杂度 $O(C^3 \times \log n)$,空间复杂度 $O(C^2)$,其中 $C$ 是元音字母的个数,本题中 $C=5$。
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 class Solution :
def countVowelPermutation ( self , n : int ) -> int :
mod = 10 ** 9 + 7
def mul ( a : List [ List [ int ]], b : List [ List [ int ]]) -> List [ List [ int ]]:
m , n = len ( a ), len ( b [ 0 ])
c = [[ 0 ] * n for _ in range ( m )]
for i in range ( m ):
for j in range ( n ):
for k in range ( len ( b )):
c [ i ][ j ] = ( c [ i ][ j ] + a [ i ][ k ] * b [ k ][ j ]) % mod
return c
def pow ( a : List [ List [ int ]], n : int ) -> List [ int ]:
res = [[ 1 ] * len ( a )]
while n :
if n & 1 :
res = mul ( res , a )
a = mul ( a , a )
n >>= 1
return res
a = [
[ 0 , 1 , 0 , 0 , 0 ],
[ 1 , 0 , 1 , 0 , 0 ],
[ 1 , 1 , 0 , 1 , 1 ],
[ 0 , 0 , 1 , 0 , 1 ],
[ 1 , 0 , 0 , 0 , 0 ],
]
res = pow ( a , n - 1 )
return sum ( map ( sum , res )) % mod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 class Solution {
private final int mod = ( int ) 1e9 + 7 ;
public int countVowelPermutation ( int n ) {
long [][] a
= {{ 0 , 1 , 0 , 0 , 0 }, { 1 , 0 , 1 , 0 , 0 }, { 1 , 1 , 0 , 1 , 1 }, { 0 , 0 , 1 , 0 , 1 }, { 1 , 0 , 0 , 0 , 0 }};
long [][] res = pow ( a , n - 1 );
long ans = 0 ;
for ( long x : res [ 0 ] ) {
ans = ( ans + x ) % mod ;
}
return ( int ) ans ;
}
private long [][] mul ( long [][] a , long [][] b ) {
int m = a . length , n = b [ 0 ] . length ;
long [][] c = new long [ m ][ n ] ;
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
for ( int k = 0 ; k < b . length ; ++ k ) {
c [ i ][ j ] = ( c [ i ][ j ] + a [ i ][ k ] * b [ k ][ j ] ) % mod ;
}
}
}
return c ;
}
private long [][] pow ( long [][] a , int n ) {
long [][] res = new long [ 1 ][ a . length ] ;
Arrays . fill ( res [ 0 ] , 1 );
while ( n > 0 ) {
if (( n & 1 ) == 1 ) {
res = mul ( res , a );
}
a = mul ( a , a );
n >>= 1 ;
}
return res ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 class Solution {
public :
int countVowelPermutation ( int n ) {
vector < vector < ll >> a = {
{ 0 , 1 , 0 , 0 , 0 },
{ 1 , 0 , 1 , 0 , 0 },
{ 1 , 1 , 0 , 1 , 1 },
{ 0 , 0 , 1 , 0 , 1 },
{ 1 , 0 , 0 , 0 , 0 }};
vector < vector < ll >> res = pow ( a , n - 1 );
return accumulate ( res [ 0 ]. begin (), res [ 0 ]. end (), 0L L ) % mod ;
}
private :
using ll = long long ;
const int mod = 1e9 + 7 ;
vector < vector < ll >> mul ( vector < vector < ll >>& a , vector < vector < ll >>& b ) {
int m = a . size (), n = b [ 0 ]. size ();
vector < vector < ll >> c ( m , vector < ll > ( n ));
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
for ( int k = 0 ; k < b . size (); ++ k ) {
c [ i ][ j ] = ( c [ i ][ j ] + a [ i ][ k ] * b [ k ][ j ]) % mod ;
}
}
}
return c ;
}
vector < vector < ll >> pow ( vector < vector < ll >>& a , int n ) {
vector < vector < ll >> res ;
res . push_back ({ 1 , 1 , 1 , 1 , 1 });
while ( n ) {
if ( n & 1 ) {
res = mul ( res , a );
}
a = mul ( a , a );
n >>= 1 ;
}
return res ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 const mod = 1e9 + 7
func countVowelPermutation ( n int ) ( ans int ) {
a := [][] int {
{ 0 , 1 , 0 , 0 , 0 },
{ 1 , 0 , 1 , 0 , 0 },
{ 1 , 1 , 0 , 1 , 1 },
{ 0 , 0 , 1 , 0 , 1 },
{ 1 , 0 , 0 , 0 , 0 }}
res := pow ( a , n - 1 )
for _ , x := range res [ 0 ] {
ans = ( ans + x ) % mod
}
return
}
func mul ( a , b [][] int ) [][] int {
m , n := len ( a ), len ( b [ 0 ])
c := make ([][] int , m )
for i := range c {
c [ i ] = make ([] int , n )
}
for i := 0 ; i < m ; i ++ {
for j := 0 ; j < n ; j ++ {
for k := 0 ; k < len ( b ); k ++ {
c [ i ][ j ] = ( c [ i ][ j ] + a [ i ][ k ] * b [ k ][ j ]) % mod
}
}
}
return c
}
func pow ( a [][] int , n int ) [][] int {
res := [][] int {{ 1 , 1 , 1 , 1 , 1 }}
for n > 0 {
if n & 1 == 1 {
res = mul ( res , a )
}
a = mul ( a , a )
n >>= 1
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 const mod = 1e9 + 7 ;
function countVowelPermutation ( n : number ) : number {
const a : number [][] = [
[ 0 , 1 , 0 , 0 , 0 ],
[ 1 , 0 , 1 , 0 , 0 ],
[ 1 , 1 , 0 , 1 , 1 ],
[ 0 , 0 , 1 , 0 , 1 ],
[ 1 , 0 , 0 , 0 , 0 ],
];
const res = pow ( a , n - 1 );
return res [ 0 ]. reduce (( a , b ) => ( a + b ) % mod );
}
function mul ( a : number [][], b : number [][]) : number [][] {
const [ m , n ] = [ a . length , b [ 0 ]. length ];
const c = Array . from ({ length : m }, () => Array . from ({ length : n }, () => 0 ));
for ( let i = 0 ; i < m ; ++ i ) {
for ( let j = 0 ; j < n ; ++ j ) {
for ( let k = 0 ; k < b . length ; ++ k ) {
c [ i ][ j ] =
( c [ i ][ j ] + Number (( BigInt ( a [ i ][ k ]) * BigInt ( b [ k ][ j ])) % BigInt ( mod ))) % mod ;
}
}
}
return c ;
}
function pow ( a : number [][], n : number ) : number [][] {
let res : number [][] = [[ 1 , 1 , 1 , 1 , 1 ]];
while ( n ) {
if ( n & 1 ) {
res = mul ( res , a );
}
a = mul ( a , a );
n >>>= 1 ;
}
return res ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 /**
* @param {number} n
* @return {number}
*/
const mod = 1e9 + 7 ;
var countVowelPermutation = function ( n ) {
const a = [
[ 0 , 1 , 0 , 0 , 0 ],
[ 1 , 0 , 1 , 0 , 0 ],
[ 1 , 1 , 0 , 1 , 1 ],
[ 0 , 0 , 1 , 0 , 1 ],
[ 1 , 0 , 0 , 0 , 0 ],
];
const res = pow ( a , n - 1 );
return res [ 0 ]. reduce (( a , b ) => ( a + b ) % mod );
};
function mul ( a , b ) {
const [ m , n ] = [ a . length , b [ 0 ]. length ];
const c = Array . from ({ length : m }, () => Array . from ({ length : n }, () => 0 ));
for ( let i = 0 ; i < m ; ++ i ) {
for ( let j = 0 ; j < n ; ++ j ) {
for ( let k = 0 ; k < b . length ; ++ k ) {
c [ i ][ j ] =
( c [ i ][ j ] + Number (( BigInt ( a [ i ][ k ]) * BigInt ( b [ k ][ j ])) % BigInt ( mod ))) % mod ;
}
}
}
return c ;
}
function pow ( a , n ) {
let res = [[ 1 , 1 , 1 , 1 , 1 ]];
while ( n ) {
if ( n & 1 ) {
res = mul ( res , a );
}
a = mul ( a , a );
n >>>= 1 ;
}
return res ;
}
方法三
Python3 Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 import numpy as np
class Solution :
def countVowelPermutation ( self , n : int ) -> int :
mod = 10 ** 9 + 7
factor = np . mat (
[
( 0 , 1 , 0 , 0 , 0 ),
( 1 , 0 , 1 , 0 , 0 ),
( 1 , 1 , 0 , 1 , 1 ),
( 0 , 0 , 1 , 0 , 1 ),
( 1 , 0 , 0 , 0 , 0 ),
],
np . dtype ( "O" ),
)
res = np . mat ([( 1 , 1 , 1 , 1 , 1 )], np . dtype ( "O" ))
n -= 1
while n :
if n & 1 :
res = res * factor % mod
factor = factor * factor % mod
n >>= 1
return res . sum () % mod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public int countVowelPermutation ( int n ) {
final int mod = 1000000007 ;
long countA = 1 , countE = 1 , countI = 1 , countO = 1 , countU = 1 ;
for ( int length = 1 ; length < n ; length ++ ) {
// Calculate the next counts for each vowel based on the previous counts
long nextCountA = countE ;
long nextCountE = ( countA + countI ) % mod ;
long nextCountI = ( countA + countE + countO + countU ) % mod ;
long nextCountO = ( countI + countU ) % mod ;
long nextCountU = countA ;
// Update the counts with the newly calculated values for the next length
countA = nextCountA ;
countE = nextCountE ;
countI = nextCountI ;
countO = nextCountO ;
countU = nextCountU ;
}
// Calculate the total count of valid strings for length n
long totalCount = ( countA + countE + countI + countO + countU ) % mod ;
return ( int ) totalCount ;
}
}
GitHub