dp问题不会做，自己值分析到斐波那契数列为止
from functools import cache
class Solution:
def findIntegers(self, n: int) -> int:
"""
0 2
00 2+1
000 2+1+2
0000 2+1+2+3
00000 2+1+2+3+5
000000 2+1+2+3+5+8
0000000 2+1+2+3+5+8+13
由规律可得n位二进数不连续为1的值的个数=(n-1)不连续为1的值的个数+(n-2)不连续为1的值的个数
Sn=(Sn-1)+(Sn-2)
是一个斐波那契序列的变种
n=1时=2，n=2时=3
使用位数DP解题
"""
s = bin(n)[2:]
n = len(s)
@cache
def dfs(cur: int, pre: int, is_limit: int) -> int:
if cur == n:
return 1
up = ord(s[cur]) - ord("0") if is_limit else 1
ans = dfs(cur + 1, 0, is_limit and up == 0)
if pre == 0 and up == 1:
ans += dfs(cur + 1, 1, is_limit)
return ans
return dfs(0, 0, 1)