问题：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;}
};