解題說明
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' 的比例在某個範圍內,問題如何建模?