1.题目基本信息

1.1.题目描述

给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。

1.2.题目地址

https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/description/

2.解题方法

2.1.解题思路

动态规划-数位dp

3.解题代码

python代码

class Solution:
    def findIntegers(self, n: int) -> int:
        @cache
        # 深度化搜索：参数：i表示当前需要填写的二进制位；pre1表示填写的前一位是否为1；isLimit表示前面填写的数字是否和n对应的二进制完全匹配，对当前的填写是否造成限制。递归函数定义：在pre1和isLimit的状态下，枚举i位的填写情况，并递归求子问题，返回可能的合法情况数。
        def dfs(i:int, pre1:bool, isLimit:bool) -> int:
            if i < 0:
                return 1
            up = (n >> i) & 1 if isLimit else 1
            # 填写0的情况
            ans = dfs(i - 1, False, isLimit and up == 0)
            if not pre1 and up == 1:
                # 填写1的情况
                ans += dfs(i - 1, True, isLimit)
            return ans
        return dfs(n.bit_length() - 1, False, True)

4.执行结果