题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是从空字符串开始，每次操作可以在字符串右侧加上 zero 个 0 或者 one 个 1，求操作完后字符串长度处于 low 和 high 的闭区间内的方案数。

思路分享

  • 这个问题可以划分为构造长度更短的子问题，而且采用“枚举选哪个”的思路，所以“易得”记忆化回溯的写法。

  • 但是在过程中要注意取模，不是说最后的结果取模，而是在回溯（递推）过程中也要做取模工作。虽然 Python 可以兼容大数字，但是对大数字进行运算的效率比较低下，所以需要取模使得运算过程保持小数字（先取模后做加法不影响结果）

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        # 递推
        f = [0] * (high+1)
        f[0] = 1
        MOD = 1_000_000_007
        for i in range(1, high+1):
            if i >= zero: f[i] = f[i-zero]
            if i >= one: f[i] = (f[i] + f[i-one]) % MOD
        return sum(f[low:]) % MOD

        # 记忆化回溯
        # @cache
        # def dfs(length)->int:
        #     res = 0
        #     if length > high:
        #         return res
        #     elif length >= low:
        #         res += 1
            
        #     res += dfs(length + zero)

        #     res += dfs(length + one)

        #     return res % (1_000_000_007)
        # return dfs(0) % (1_000_000_007)