題目描述:
給定整數 low、high、zero 和 one。從空字串開始,每步可以追加 zero 個 '0' 或 one 個 '1'。求長度在 [low, high] 範圍內的「好字串」的數量,結果對 10^9 + 7 取模。
解題思路: 這是一個典型的爬樓梯/組合 DP 問題:
dp[i] = 構造長度恰好為 i 的字串的方法數。dp[i] = dp[i - zero] + dp[i - one](若索引合法)。dp[0] = 1(空字串是唯一的長度 0 字串)。sum(dp[low..high])。時間複雜度:O(high) — 計算 DP 到 high。
空間複雜度:O(high) — DP 陣列大小為 high + 1。
1. Initialize dp[0..high] = 0, dp[0] = 1 2. Set ans = 0 3. For i from 1 to high: a. If i >= zero: dp[i] += dp[i - zero] b. If i >= one: dp[i] += dp[i - one] c. Take modulo d. If i >= low: ans += dp[i] 4. Return ans % MOD
記憶化搜尋 O(high):遞迴定義 dfs(len) = 從長度 len 開始能構造的方法數。每次可以加 zero 或 one。用記憶化避免重複計算。
矩陣快速冪 O(log high):若 zero 和 one 較小,可以將 DP 轉移表示為矩陣乘法,用快速冪在 O(max(zero, one)^3 * log high) 時間內求解。適用於 high 極大的情況。