leetcode
leetcode 2151 ~ 2200
统计构造好字符串的方案数

统计构造好字符串的方案数

难度:

标签:

题目描述

代码结果

运行时间: 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[0]为1是因为长度为0的字符串(即空字符串)只有一种构造方式,就是什么也不做。这个初始化提供了递推的基础,使得当我们在计算更长的字符串的方案数时,可以正确地从这个基础情况累加起来。
🦆
在更新dp数组时,为什么要对每个长度先检查是否可以从长度i-one或i-zero来通过添加'1'或'0'达到长度i?
在更新dp数组时,检查长度i-one和i-zero是为了确保只有当当前长度i减去添加的字符'1'或'0'的数目(one或zero)仍然为非负时,这种构造方式才是有效的。这样的检查确保我们可以从一个有效的较短字符串通过添加相应数量的'1'或'0'来构造出长度为i的字符串。这也避免了指向dp数组无效索引的错误访问。
🦆
你是如何保证在计算过程中不会重复计算相同长度的字符串的构造方案数?
在这个动态规划算法中,每个dp[i]只被计算一次,并且每次计算都是基于前面的结果dp[i-one]和dp[i-zero]。通过这种方式,我们确保了在计算dp[i]时,之前计算的每个字符串长度的方案数都已被考虑,而不会被重复计算。这种从小到大计算并存储结果的方法避免了重复计算的问题。
🦆
在计算low到high长度的字符串的总方案数时,为什么要使用求和然后取余的方法?
使用求和然后取余的方法是为了防止在累加过程中结果数值过大导致的整数溢出问题,同时也是为了满足可能的计算结果要求。MOD通常是一个大质数,如10^9+7,它可以确保结果在一个可管理的范围内,并且取余操作是在确保在数学上结果仍然正确的前提下,符合给定的模数约束。

相关问题