Non-negative Integers without Co

参考如下link:
https://discuss.leetcode.com/topic/90571/java-solution-dp

这样的题原来是可以拿dp做的，从len = 1 dp推广到 len = n. 需要注意的是这道题是要小于某个数，而不是小于某个长度，所以如果原数有'00'，比如4，最终结果需要去掉101这个情况，而这种情况恰好是b[i-1];

class Solution {
public:
    
    string toBinaryString(int num){
        string ret;
        int mask = 1;
        while(num >= mask){
            if((num & mask) >= 1) ret = '1' + ret;
            else ret = '0' + ret;
            mask <<= 1;
        }
        return ret;
    }

    int findIntegers(int num) {
        if(num <= 0) return 0;
        string s = toBinaryString(num);
        //cout << s << endl;
        int len = s.length();
        int a[len], b[len];
        a[0] = b[0] = 1;
        for(int i=1; i<len; i++){
            a[i] = a[i-1] + b[i-1];
            b[i] = a[i-1];
        }
        int res = a[len-1] + b[len-1];
        reverse(s.begin(), s.end());
        for(int i=len-2; i>=0; i--){
            if(s[i] == '1' && s[i+1] == '1') break;
            else if(s[i] == '0' && s[i+1] == '0') res -= b[i];
        }
        return res;
    }
};