構造字符串，每次可以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