一開始寫成recursive+memorize 整個超爆幹慢
給gemini改成non-recursive 果然快了不少==
我好爛
def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
dp = [0] * (high+1)
dp[0] = 1
mod = 10**9 + 7
for i in range(1, high+1):
if i>=zero:
dp[i] = (dp[i] + dp[i-zero]) % mod
if i>=one:
dp[i] = (dp[i] + dp[i-one]) % mod
ans = 0
for j in range(low, high+1):
ans = (ans + dp[j]) % mod
return ans