Digit DP

600. Non-negative Integers without Consecutive Ones

The following code is adjusted from [3]. Credit goes to 66brother.

const int BITS = 32, SAME = 2, PREV = 2, CONSEC = 2;
int f[BITS][SAME][PREV][CONSEC];
class Solution {
public:
    int dp( vector<int>& bits, int i, int same, int prev, int consec){
        if (i == bits.size()) return consec ? 0 : 1;
        if (f[i][same][prev][consec] != -1) return f[i][same][prev][consec];
        int ret = 0, newprev = 0, newsame = 0, newconsec = 0;
        int bit = bits[i];
        if (bit == 0)
        {
            // if the previous bits are same, then we can only choose 0
            if (same)
            {
                newprev = 0;
                ret += dp(bits, i + 1, same, newprev, consec);
            } else 
            // if the previous bits are not the same, as previous bits are higher bits, if we choose
            // 1, the new number is still < n. It is valid. We can choose both 0 and 1
            {
                // choose 0
                newprev = 0;
                ret += dp(bits, i + 1, same, newprev, consec);
                // choose 1
                newprev = 1;
                // if already consec, of it is still consec. If not consec, check whether the old prev and the current value are the same.
                newconsec = consec? consec : prev == newprev; 
                ret += dp(bits, i + 1, same, newprev, newconsec);
            }
        } else { // bit = 1. we can choose both 0 or 1.
            newprev = 0;
            newsame = 0;
            ret += dp(bits, i + 1, newsame, newprev, consec);
            newprev = 1;
            newconsec = consec? consec : prev == newprev; 
            ret += dp(bits, i + 1, same, newprev, newconsec);
        }
        return f[i][same][prev][consec] = ret;
    }
    
    int findIntegers(int n) {
        // digit dp
        // do not contain CONSEC
        memset(f, -1, sizeof f);
        vector<int> bits;
        while(n){
            bits.push_back(n&1);
            n >>= 1;
        }
        reverse(bits.begin(), bits.end());
        const int m = bits.size();
        int i = 0, same = 1, prev = 0,  consec = 0;
        return dp(bits, i, same, prev, consec); 
    }
};

Reference

[1]https://www.geeksforgeeks.org/digit-dp-introduction/

[2] https://oi-wiki.org/dp/number/

[3]https://youtu.be/C3w3qcCGU4Q