给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。
示例 1:
输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
数位DP傻逼题，直接套即可。详情见注释。
#include <bits/stdc++.h>
using namespace std;
int n, num[100], len = 1;
int dp[66][2][2];
int dfs(int len, int pre, bool tight) {//len是当前枚举到的位 pre是上一位 tight表示之前是否紧贴边界
if(dp[len][pre][tight]) return dp[len][pre][tight];
if(len == 0) return 1;
int ans = 0;
for(int i = 0; i <= 1; i++) {
if(i == 0) {//后面的可以随便取
ans += dfs(len - 1, 0, tight && (i == num[len]));
} else {//这一位如果是1的话，上一位肯定不能是1，同时要注意不能超边界
if(pre == 1 || (i > num[len] && tight)) continue;
ans += dfs(len - 1, 1, tight && (i == num[len]));
}
}
return dp[len][pre][tight] = ans;
}
int calc(int x) {
while(x) {
int now = x % 2;
num[len++] = now;
x /= 2;
}
len--;
return dfs(len, 0, 1);
}
int main() {
cin >> n;
cout << calc(n);
return 0;
}