<p>Given a positive integer <code>n</code>, return the number of the integers in the range <code>[0, n]</code> whose binary representations <strong>do not</strong> contain consecutive ones.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 5
<strong>Output:</strong> 5
<strong>Explanation:</strong>
Here are the non-negative integers &lt;= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    string binConvert(int n) {
        string res = "";
        while (n > 0) {
            res.push_back((n % 2) + '0');
            n /= 2;
        }
        reverse(res.begin(), res.end());
        return res;
    }

    int fun(string &s, int ind, int tight, int prev, vector<vector<vector<int>>> &dp) {
        int n = s.size();
        if (ind == n)
            return 1;
        if (dp[ind][tight][prev] != -1)
            return dp[ind][tight][prev];
        int limit = tight ? (s[ind] - '0') : 1;
        int ans = 0;
        for (int i = 0; i <= limit; i++) {
            if (i == 1 && prev == 1) 
                continue;
            ans += fun(s, ind + 1, tight & (i == limit), i, dp);
        }
        return dp[ind][tight][prev] = ans;
    }

    int findIntegers(int n) {
        string s = binConvert(n);
        int m = s.size();
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(2, vector<int>(2, -1)));
        return fun(s, 0, 1, 0, dp);
    }
};

11400