Số nguyên không âm không có 1 liên tiếp (Non-negative Integers without Consecutive Ones) trong C++

Cho số nguyên dương n. Đếm số nguyên không âm ≤ n mà biểu diễn nhị phân không chứa 2 bit 1 liên tiếp.

Ví dụ

n=7 (111) → kết quả 5 (các số: 0,1,2,4,5).

DP trên bit (Fibonacci)

Số dãy nhị phân độ dài i không có 11 liên tiếp: fib[i+2]. Duyệt bit từ cao xuống thấp, nếu gặp "11" thì dừng. Nếu bit hiện tại và bit trước đều 0, trừ đi số dãy bắt đầu bằng 11 tại vị trí đó.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    string toBinary(int n) {
        string s;
        while(n) { s.push_back('0'+(n&1)); n>>=1; }
        reverse(s.begin(), s.end());
        return s.empty() ? "0" : s;
    }
public:
    int findIntegers(int num) {
        string bits = toBinary(num);
        int n = bits.size();
        vector<int> zero(n), one(n);
        zero[0]=one[0]=1;
        for(int i=1;i=0;i--) {
            if(bits[i]=='0' && bits[i+1]=='0') ans -= one[i];
            else if(bits[i]=='1' && bits[i+1]=='1') break;
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.findIntegers(7); // 5
    return 0;
}