Leetcode 2466. 统计构造好字符串的方案数 入门dp(取模) C++实现

题目：Leetcode 2466. 统计构造好字符串的方案数
        给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步实验下面利用中的一种：

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

以上利用可以实验恣意次。
        如果通过以上过程得到一个 长度 在 low 和 high 之间（包罗上下边界）的字符串，那么这个字符串我们称为 好 字符串。
        请你返回满足以上要求的 差别 好字符串数目。由于答案大概很大，请将结果对 10⁹ + 7  取余 后返回。

---

算法1：影象化搜索

代码：

1. class Solution {
2. public:
3.     int countGoodStrings(int low, int high, int zero, int one) {
4.         vector<int> memo(high + 1,-1);
5.         auto dfs = [&](auto &&dfs,int i){
6.             if(i < 0)   return 0;
7.             if(i == 0)  return 1;
8.             int& res = memo[i];
9.             if(res != -1)   return res;
10.             return res = dfs(dfs,i - zero) + dfs(dfs,i - one);
11.         };
12.         int ans = 0;
13.         for(int j = low;j <= high;j++)
14.             ans += dfs(dfs,j);
15.         return ans;
16.     }
17. };

复制代码

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

1. class Solution {
2. public:
3.     int countGoodStrings(int low, int high, int zero, int one) {
4.         const int MOD = 1'000'000'007;
5.         vector<int> memo(high + 1,-1);
6.         auto dfs = [&](auto &&dfs,int i){
7.             if(i < 0)   return 0;
8.             if(i == 0)  return 1;
9.             int& res = memo[i];
10.             if(res != -1)   return res;
11.             //return res = dfs(dfs,i - zero) + dfs(dfs,i - one);
12.             return res = (dfs(dfs, i - zero) + dfs(dfs, i - one)) % MOD;
13.         };
14.         int ans = 0;
15.         for(int j = low;j <= high;j++)
16.             //ans += dfs(dfs,j);
17.             ans = (ans + dfs(dfs, j)) % MOD;
18.         return ans;
19.     }
20. };

复制代码

---

算法2：递推
代码：

1. class Solution {
2. public:
3.     int countGoodStrings(int low, int high, int zero, int one) {
4.         const int MOD = 1'000'000'007;
5.         vector<int> dp(high + 1); // dp[i] 表示构造长为 i 的字符串的方案数
6.         int ans = 0;
7.         dp[0] = 1; // 构造空串的方案数为 1
8.         for(int i = 1;i <= high;i++){
9.             if(i >= zero)   dp[i] = dp[i - zero];
10.             if (i >= one)  dp[i] = (dp[i] + dp[i - one]) % MOD;
11.             if (i >= low)  ans = (ans + dp[i]) % MOD;
12.         }
13.         return ans;
14.     }
15. };

复制代码