解題說明
Count Ways To Build Good Strings
題目描述：
給定整數 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])。
C++ 解法
複雜度分析
時間複雜度：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 極大的情況。
延伸思考
- 此題與「爬樓梯」（Climbing Stairs）問題有什麼結構上的相似性？
- 如果每步可以追加的字元種類超過兩種，DP 轉移如何修改？
- 如果要求字串中 '0' 和 '1' 的比例在某個範圍內，問題如何建模？