力扣2466详解：动态规划巧解字符串构造问题
一、问题理解
我们需要计算通过特定操作构造的字符串数量，这些字符串的长度必须在给定范围内。每次操作可以选择添加固定数量的'0'或'1'。
二、解题思路
动态规划定义：dp[i]表示长度为i的字符串的构造方式数
状态转移：
dp[i] += dp[i-zero] (如果可以添加zero个'0')
dp[i] += dp[i-one] (如果可以添加one个'1')
结果计算：累加dp[low]到dp[high]的值
三、代码详解
class Solution {
public:
int countGoodStrings(int low, int high, int zero, int one) {
const int MOD = 1e9 + 7;
vector<int> dp(high + 1, 0);
dp[0] = 1; // 空字符串有一种构造方式
for (int i = 1; i <= high; ++i) {
// 如果可以在末尾添加zero个'0'
if (i >= zero) {
dp[i] = (dp[i] + dp[i - zero]) % MOD;
}
// 如果可以在末尾添加one个'1'
if (i >= one) {
dp[i] = (dp[i] + dp[i - one]) % MOD;
}
}
// 累加所有在[low, high]范围内的方案数
int result = 0;
for (int i = low; i <= high; ++i) {
result = (result + dp[i]) % MOD;
}
return result;
}
};四、复杂度分析
五、优化思考
可以优化空间复杂度到O(max(zero,one))
预处理zero和one的最小公倍数可能有优化空间
原创内容 转载请注明出处
