2466. 統計構造好字符串的方案數 - 力扣（LeetCode）

這個問題可以用**動態規劃（DP）**來解決，思路如下：

---

思路

1. 定義 DP 數組

設 dp[i] 表示長度為 i 的好字符串的個數。

2. 狀態轉移方程

• 我們可以在 dp[i] 的基礎上添加 zero 個 '0'，得到 dp[i + zero]。
• 或者在 dp[i] 的基礎上添加 one 個 '1'，得到 dp[i + one]。

因此，狀態轉移方程為：dp[i]=dp[i?zero]+dp[i?one]

需要對 10^9 + 7 取模。

3. 初始化

• dp[0] = 1，表示空字符串。

4. 目標

• 我們要求 low ≤ i ≤ high 之間的所有 dp[i] 的總和。

---

代碼實現

def countGoodStrings(low: int, high: int, zero: int, one: int) -> int:MOD = 10**9 + 7dp = [0] * (high + 1)dp[0] = 1  # 空字符串# 計算 dpfor i in range(1, high + 1):if i >= zero:dp[i] = (dp[i] + dp[i - zero]) % MODif i >= one:dp[i] = (dp[i] + dp[i - one]) % MOD# 計算 [low, high] 之間的總和return sum(dp[low: high + 1]) % MOD

---

復雜度分析

• 時間復雜度：O(high)。
• 空間復雜度：O(high)。

---

示例

輸入

print(countGoodStrings(2, 3, 1, 2))

輸出

5

解釋

滿足條件的字符串：

• "00"，"11"，"01"，"10"，"001"。

---

優化

由于 dp[i] 只依賴于前面的 dp[i-zero] 和 dp[i-one]，可以用一個變量存儲 dp[low] 到 dp[high] 之間的和，減少不必要的計算：

def countGoodStrings(low: int, high: int, zero: int, one: int) -> int:MOD = 10**9 + 7dp = [1] + [0] * highresult = 0for i in range(1, high + 1):if i >= zero:dp[i] = (dp[i] + dp[i - zero]) % MODif i >= one:dp[i] = (dp[i] + dp[i - one]) % MODif i >= low:result = (result + dp[i]) % MOD  # 直接求和return result

這樣可以避免額外的 sum() 計算，使得代碼更高效！🚀