参考如下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;
}
};
