Description
給定
low,high,zero,one。每步可以在字串末尾加上zero個 ‘0’ 或one個 ‘1’。求長度在[low, high]之間的「好字串」有多少個，結果對10^9 + 7取模。
Example:
Input: low = 3, high = 3, zero = 1, one = 1 Output: 8
Intuition#
Climbing Stairs 的變體 — 每步可以跳
zero格或one格，求到達 [low, high] 範圍內任何位置的方法總數。
dp[i]= 建出長度恰好為i的字串的方法數- 狀態轉移：
dp[i] = dp[i - zero] + dp[i - one] - 最終答案：
sum(dp[low..high])
Approaches#
1: Top-Down Memoization#
- 概念: 遞迴嘗試加 zero 或 one 個字元，記憶化
- 時間複雜度:
O(high) - 空間複雜度:
O(high)
class Solution {
fun countGoodStrings(low: Int, high: Int, zero: Int, one: Int): Int {
val MOD = 1_000_000_007
val memo = IntArray(high + 1) { -1 }
fun dp(len: Int): Int {
if (len > high) return 0
if (memo[len] != -1) return memo[len]
var res = if (len >= low) 1 else 0
res = (res + dp(len + zero)) % MOD
res = (res + dp(len + one)) % MOD
memo[len] = res
return res
}
return dp(0)
}
}⭐2: Bottom-Up DP#
- 概念: 從長度 0 到 high 逐步計算方法數，累加 [low, high] 範圍的答案
- 時間複雜度:
O(high) - 空間複雜度:
O(high)
class Solution {
fun countGoodStrings(low: Int, high: Int, zero: Int, one: Int): Int {
val MOD = 1_000_000_007
val dp = IntArray(high + 1)
dp[0] = 1
var ans = 0
for (i in 1..high) {
if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % MOD
if (i >= one) dp[i] = (dp[i] + dp[i - one]) % MOD
if (i in low..high) ans = (ans + dp[i]) % MOD
}
return ans
}
}🔑 Takeaways#
- Pattern: Climbing Stairs 推廣 — 步長從固定的 1/2 變成可變的 zero/one
- 關鍵技巧: 不要被字串描述迷惑，本質上就是「幾種方式走到某個長度」的計數問題