Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

由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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理