Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
构造字符串,每次可以append zero个0,或者one个1,问长度为[low, high]的字符串有多少种构造方式(mod 10^9+7),DP


 1 #2466
 2 #Runtime: 145 ms (Beats 100%)
 3 #Memory: 19.5 MB (Beats 100%)
 4 
 5 class Solution(object):
 6     def countGoodStrings(self, low, high, zero, one):
 7         """
 8         :type low: int
 9         :type high: int
10         :type zero: int
11         :type one: int
12         :rtype: int
13         """
14         dp = [0] * (high + 1)
15         dp[0] = 1
16         MOD = 10 ** 9 + 7
17         ans = 0
18         for i in range(min(zero, one), high + 1):
19             if i >= zero:
20                 dp[i] = (dp[i] + dp[i - zero]) % MOD
21             if i >= one:
22                 dp[i] = (dp[i] + dp[i - one]) % MOD
23         for i in range(low, high + 1):
24             ans = (ans + dp[i]) % MOD
25         return ans

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