不含连续1的非负整数

Leetcode Link: 600. 不含连续1的非负整数 - 力扣（LeetCode）

题目

解法一

思路：数位 dp

实际上本题的关键在于把十进制转换成二进制就可以了，开始就是卡在了这里。 注意 bin(num) >>> '0b100101001'，需要取 [2:]

题解：

class Solution:
    def findIntegers(self, n: int) -> int:
        s = bin(n)[2:]
        
        memo = {}
        def process(i, pre, is_bound):
        '''
	        i: 当前位置
	        pre: 前一个位置的数字
	        is_bound: 是否贴边放置
        '''
            if i == len(s):
                return 1
            
            if not is_bound and (i, pre) in memo.keys():
                return memo[(i, pre)]
            
            maxi = int(s[i]) if is_bound else 1
            res = 0
            for val in range(maxi+1):
                if pre == val == 1:  # 保证没有连续1就行
                    continue
                else:
                    res += process(i+1, val, is_bound and val == maxi)
            
            if not is_bound: memo[(i, pre)] = res
            return res
 
        return process(0, 0, True)