统计构造好字符串的方案数
难度:
标签:
题目描述
代码结果
运行时间: 91 ms, 内存: 20.3 MB
/*
* 思路:
* 使用Java Stream来处理。思路与普通Java版本一致,只是在遍历和累加上使用了Stream API。
*/
import java.util.stream.IntStream;
public class GoodStringCounterStream {
public int countGoodStrings(int low, int high, int zero, int one) {
final int MOD = 1000000007;
int[] dp = new int[high + 1];
dp[0] = 1;
IntStream.rangeClosed(1, high).forEach(i -> {
if (i >= zero) {
dp[i] = (dp[i] + dp[i - zero]) % MOD;
}
if (i >= one) {
dp[i] = (dp[i] + dp[i - one]) % MOD;
}
});
return IntStream.rangeClosed(low, high).reduce(0, (result, i) -> (result + dp[i]) % MOD);
}
}
解释
方法:
本题解使用了动态规划的方法来计算所有可能的好字符串的数目。定义dp数组,其中dp[i]表示长度为i的字符串的构造方案数。数组初始化为dp[0] = 1(空字符串有一种构造方式),其余为0。对于每个长度i(从1到high),更新dp[i]的值,通过检查是否可以从长度i-one或i-zero的字符串通过添加'1'或'0'来达到长度i。最后,将low到high之间的所有dp值求和得到答案。
时间复杂度:
O(high)
空间复杂度:
O(high)
代码细节讲解
🦆
在动态规划算法中,为什么初始化dp[0]为1?
▷🦆
在更新dp数组时,为什么要对每个长度先检查是否可以从长度i-one或i-zero来通过添加'1'或'0'达到长度i?
▷🦆
你是如何保证在计算过程中不会重复计算相同长度的字符串的构造方案数?
▷🦆
在计算low到high长度的字符串的总方案数时,为什么要使用求和然后取余的方法?
▷