600.不含连续1的非负整数

题目

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 **连续的1 **的个数。

示例 1:

输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

说明: 1 <= n <= 109

思路

说实话没怎么懂，看 @宫水三叶 的讲解，抄了抄代码。
@宫水三叶的 讲解

这是一道典型的「数位 DP」题。

对于「数位 DP」题，都存在「询问 [ a , b ] [a, b] [a,b]（ a a a 和 b b b 均为正整数，且 a < b a < b a<b）区间内符合条件的数值个数为多少」的一般形式，通常我们需要实现一个查询 [ 0 , x ] [0, x] [0,x] 有多少合法数值的函数 int dp(int x)，然后应用「容斥原理」求解出 [ a , b ] [a, b] [a,b] 的个数： d p ( b ) − d p ( a − 1 ) dp(b) - dp(a - 1) dp(b)−dp(a−1)。
对于本题，虽然只需要求解 [ 0 , n ] [0, n] [0,n] 范围内数的个数，但其实拓展到求 [ a , b ] [a, b] [a,b] 区间个数的也不会增加难度。

具体的，对于「数位 DP」问题通常是「从高位到低位」的分情况讨论。

不失一般性的考虑数值 n n n 的某一位 c u r cur cur 是如何被处理的：

1. 如果当前位 c u r = 1 cur = 1 cur=1 的话，由于我们需要满足「小于等于 n n n」的要求，因此如果该位填 0 0 0 的话，后面的低位填什么都是满足要求的，因此我们期望能够查表得出「长度为 i + 1 i + 1 i+1，且二进制位置 i i i 数值为 0 0 0 时」有多少合法数值，将其累加到答案中；
   与此同时，我们需要确保当前位选 1 1 1 是合法的，即我们需要记录上一位 p r e v prev prev 是什么，确保 c u r cur cur 和 p r e v prev prev 不同时为 1 1 1。
2. 如果当前位 c u r = 0 cur = 0 cur=0 的话，我们只能选 0 0 0，并决策下一位。

当出现「当前位无法填入 c u r cur cur」或者「决策到最低位」时，则完成了所有合法答案的统计。

至于流程 1 1 1 中的查表操作，我们可以使用 static 预处理出 f 数组，定义 f [ i ] [ j ] f[i][j] f[i][j] 为考虑二进制长度为 i i i，且最高位为 j j j（ 0 0 0 or 1 1 1）时的合法数个数。

注意：为了防止重复计数问题，我们在不失一般性的计算 f [ i ] [ 0 ] f[i][0] f[i][0] 和 f [ i ] [ 1 ] f[i][1] f[i][1] 时，不能采用诸如 f [ i ] [ c u r ] + = f [ i − 1 ] [ p r e v ] f[i][cur] += f[i - 1][prev] f[i][cur]+=f[i−1][prev] 的 “后向查找依赖” 的方式进行转移，而要采用 f [ i + 1 ] [ c u r ] + = f [ i ] [ p r e v ] f[i + 1][cur] += f[i][prev] f[i+1][cur]+=f[i][prev] “前向主动更新” 的方式进行转移。

不失一般性的考虑 f [ i ] [ 0 ] f[i][0] f[i][0] 和 f [ i ] [ 1 ] f[i][1] f[i][1] 能够更新哪些状态：

• 如果期望当前位填 0 0 0 的话，需要统计所有满足 ( 0… ) 2 (0…)_2 (0…)2​ 形式的合法数值，当前位的低一位只能填 1 1 1（填 0 0 0 会出现重复计数，即需要忽略前导零的数值），此时有： f [ i + 1 ] [ 0 ] = f [ i ] [ 1 ] f[i + 1][0] = f[i][1] f[i+1][0]=f[i][1]；

• 如果期望当前位填 1 1 1 的话，需要统计所有满足 ( 1… ) 2 (1…)_2 (1…)2​ 和 ( 0… ) 2 (0…)_2 (0…)2​ 形式的合法数值：

• ( 1… ) 2 (1…)_2 (1…)2​ 时，当前位的低一位只能填 0 0 0；此时有： f [ i + 1 ] [ 1 ] + = f [ i ] [ 0 ] f[i + 1][1] += f[i][0] f[i+1][1]+=f[i][0]； * ( 0… ) 2 (0…)_2 (0…)2​ 时，当前位的低一位只能填 1 1 1；此时有： f [ i + 1 ] [ 1 ] + = f [ i ] [ 1 ] f[i + 1][1] += f[i][1] f[i+1][1]+=f[i][1]。

代码

class Solution {
public:
    int findIntegers(int n) {
        if(!n) return 1;
        int N = 32;
        int dp[N][2];
        memset(dp,0,sizeof(int)*N*2);
        dp[1][0] = 1;
        dp[1][1] = 2;
        for(int i=1;i<N-1;++i){
            dp[i+1][0] = dp[i][1];
            dp[i+1][1] = dp[i][0]+dp[i][1];
        }
        int pre = 0,ans=0,idx=31;
        for(;idx>=0;--idx){
            if(((n>>idx)&1)==1) break;
        }
        for(;idx>=0;--idx){
            int cur = (n>>idx)&1;
            if(cur==1) ans+=dp[idx+1][0];
            if(pre==1&&cur==1) break;
            pre=cur;
            if(idx==0) ans++;
        }
        return ans;
    }
};