Non-negative Integers without Consecutive Ones LeetCode solution in Python

1
class Solution:
2
    def findIntegers(self, n: int) -> int:
3
        b = bin(n).replace("0b", "")
4
        dp = [
5
            [[[-1 for i in range(2)] for i in range(2)] for i in range(2)]
6
            for i in range(30)
7
        ]
8

9
        def fun(i, last, tight, leading_zeros):
10
            if i == len(str(b)):
11
                return 1
12
            if dp[i][tight][leading_zeros][last] != -1:
13
                return dp[i][tight][leading_zeros][last]
14
            end = 1
15
            if tight == 1:
16
                end = int(b[i])
17
            res = 0
18
            for j in range(end + 1):
19
                if j == 0 and leading_zeros == 1:
20
                    res += fun(i + 1, j, tight & int(j == end), 1)
21
                else:
22
                    if j == 0:
23
                        res += fun(i + 1, j, tight & int(j == end), 0)
24
                    else:
25
                        if last != j:
26
                            res += fun(i + 1, j, tight & int(j == end), 0)
27
            dp[i][tight][leading_zeros][last] = res
28
            return res
29

30
        return fun(0, 0, 1, 1)