Description
给出\(n\)，返回区间\([0,n]\)内不含连续二进制1的数位的数字个数
Constraints
\(1 \le n \le 10^9\)
Solution
数位DP直接解
Code
class Solution {
public:
int findIntegers(int n) {
// dp[i][j]: answer calculated from `i` to +inf digits where last is `j`
// i: length of digits
// j: last is 1?
int dp[35][2];
memset(dp, -1, sizeof dp);
int a[35] {};
int len = 0;
for(auto m {n}; m; m >>= 1) {
a[len++] = m & 1;
}
auto DP = [&](auto &&DP, int cur, bool limit, bool last1) {
if(cur == -1) return 1;
if(!limit && ~dp[cur][last1]) return dp[cur][last1];
int up = limit ? a[cur] : 1;
int ans = 0;
for(int i = 0; i <= up; ++i) {
if(i == 1 && last1) continue;
ans += DP(DP, cur-1, limit && i == a[cur], i == 1);
}
return limit ? ans : dp[cur][last1] = ans;
};
return DP(DP, len-1, true, false);
}
};