Posted on 2023-10-31 17:20
Uriel 閱讀(35)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
由a,e,i,o,u構成字符串，要求：
- a -> e, i and u
- e -> a and i
- i -> e and o
- o -> i
- u -> i and o
問長度n的字符串有幾種構成方式，DP
1 #1220
2 #Runtime 142 ms Beats 77.78%
3 #Memory 17.8 MB Beats 55.56%
4
5 class Solution(object):
6 def countVowelPermutation(self, n):
7 """
8 :type n: int
9 :rtype: int
10 """
11 dp = [[1] * 5] + [[0] * 5 for _ in range(n - 1)]
12 MOD = 10**9 + 7
13 for i in xrange(1, n):
14 dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4]) % MOD
15 dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD
16 dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % MOD
17 dp[i][3] = (dp[i - 1][2]) % MOD
18 dp[i][4] = (dp[i - 1][2] + dp[i - 1][3]) % MOD
19 return sum(dp[-1]) % MOD