Description

给出\(n\),返回区间\([0,n]\)内不含连续二进制1的数位的数字个数

Constraints

\(1 \le n \le 10^9\)

Solution

数位DP直接解

Code

class Solution {
public:
    int findIntegers(int n) {
        // dp[i][j]: answer calculated from `i` to +inf digits where last is `j`
        // i: length of digits
        // j: last is 1?
        int dp[35][2];
        memset(dp, -1, sizeof dp);
        
        int a[35] {};
        int len = 0;
        for(auto m {n}; m; m >>= 1) {
            a[len++] = m & 1;
        }

        auto DP = [&](auto &&DP, int cur, bool limit, bool last1) {
            if(cur == -1) return 1;
            if(!limit && ~dp[cur][last1]) return dp[cur][last1];
            int up = limit ? a[cur] : 1;
            int ans = 0;
            for(int i = 0; i <= up; ++i) {
                if(i == 1 && last1) continue;
                ans += DP(DP, cur-1, limit && i == a[cur], i == 1);
            }
            return limit ? ans : dp[cur][last1] = ans;
        };

        return DP(DP, len-1, true, false);
    }
};

LeetCode-600 Non-negative Integers without Consecutive Ones