问题：Leetcode 2466. 统计构造好字符串的方案数

        给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

• 将 '0' 在字符串末尾添加 zero  次。
• 将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

        如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。

        请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 10⁹ + 7  取余 后返回。

---

算法1：记忆化搜索

代码：

class Solution {
public:int countGoodStrings(int low, int high, int zero, int one) {vector<int> memo(high + 1,-1);auto dfs = [&](auto &&dfs,int i){if(i < 0)   return 0;if(i == 0)  return 1;int& res = memo[i];if(res != -1)   return res;return res = dfs(dfs,i - zero) + dfs(dfs,i - one);};int ans = 0;for(int j = low;j <= high;j++)ans += dfs(dfs,j);return ans;}
};

加入取模操作，详见 Leetcode 50. Pow(x,n) 快速幂 取模

class Solution {
public:int countGoodStrings(int low, int high, int zero, int one) {const int MOD = 1'000'000'007;vector<int> memo(high + 1,-1);auto dfs = [&](auto &&dfs,int i){if(i < 0)   return 0;if(i == 0)  return 1;int& res = memo[i];if(res != -1)   return res;//return res = dfs(dfs,i - zero) + dfs(dfs,i - one);return res = (dfs(dfs, i - zero) + dfs(dfs, i - one)) % MOD;};int ans = 0;for(int j = low;j <= high;j++)//ans += dfs(dfs,j);ans = (ans + dfs(dfs, j)) % MOD;return ans;}
};

---

算法2：递推

代码：

class Solution {
public:int countGoodStrings(int low, int high, int zero, int one) {const int MOD = 1'000'000'007;vector<int> dp(high + 1); // dp[i] 表示构造长为 i 的字符串的方案数int ans = 0;dp[0] = 1; // 构造空串的方案数为 1for(int i = 1;i <= high;i++){if(i >= zero)   dp[i] = dp[i - zero];if (i >= one)  dp[i] = (dp[i] + dp[i - one]) % MOD;if (i >= low)  ans = (ans + dp[i]) % MOD;}return ans;}
};