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

给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。

示例 1:

输入: n = 5
输出: 5
解释:
下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数 3 违反规则（有两个连续的 1 ），其他 5 个满足规则。
示例 2:

输入: n = 1
输出: 2
示例 3:

输入: n = 2
输出: 3

提示:

1 <= n <= 109

解题思路

这题是困难题，应该不止一个点要考虑。

前言：很多人看到 LeetCode 上的 Hard 标签和“数位 DP”几个字就想直接“早点睡吧”。但其实，很多看似高深莫测的 Hard 题，剥开抽象的外壳后，逻辑异常优雅。今天我们就以 LeetCode 600. 不含连续 1 的非负整数 为例，从一个新人的思考视角，一步步推导并破解这道题！

---

新人的第一直觉（暴力解法）

最直接的想法：从 0 遍历到 n，检查每一个数的二进制是否有连续 1。
用位运算判断连续 1 极其简单：(x & (x >> 1)) != 0。

int count = 0;
for (int i = 0; i <= n; i++) {
    if ((i & (i >> 1)) == 0) {
        count++;
    }
}
return count;

问题出在哪里？
题目给出的数据范围是 1 <= n <= 10^9。O(n) 的时间复杂度遍历十亿次，系统必定抛给你一个惨绝人寰的 Time Limit Exceeded（超时）。

必须寻找降维打击的方法！

---

破局点一：如果不考虑上限 n，规律是什么？

很多动态规划问题的破局点在于：先不考虑上限限制，看看无拘无束时有什么规律。

假设我们现在要构造一个长度为 i 的二进制串，且不能出现连续的 1，一共有多少种填法？

我们从最高位（第 i 位）开始往下填：

1. 如果最高位填 0：
   • 后面剩下的 i-1 位可以任意合法填写。
   • 方案数等于：长度为 i-1 的合法方案数。
2. 如果最高位填 1：
   • 为了不破坏“无连续 1”的规则，第二高位必须强制填 0！
   • 填完 10 之后，剩下的 i-2 位可以任意合法填写。
   • 方案数等于：长度为 i-2 的合法方案数。

把这两种独立的情况相加，递推公式赫然显现：

• dp[i] = dp[i-1] + dp[i-2]

这不就是我们最熟悉的斐波那契数列吗？！

我们来手算出几个边界条件验证一下：

• dp[0] = 1 （长度为 0 的空串，只有 1 种方案）
• dp[1] = 2 （长度为 1，可填 0, 1，共 2 种）
• dp[2] = 3 （长度为 2，可填 00, 01, 10，共 3 种）
• dp[3] = 5 （长度为 3，可填 000, 001, 010, 100, 101，共 5 种）

有了这个预处理数组，任意长度的自由组合方案数我们都了如指掌了。但现在真正的难点来了——如何限制生成的数不超过 n？

---

破局点二：试填与分支（数位 DP 核心思想）

面对上限 n，数位 DP 的核心精髓是：从高位到低位逐位试填，将解空间切分为“已确定小于 n 的分支”和“紧贴上限 n 的分支”。

假设 n = 5，二进制表示为 1 0 1（从高位到低位依次是第 2 位、第 1 位、第 0 位）：

我们从最高位（第 2 位）开始往低位扫描：

第一步：扫描第 2 位（值为 1）

• 分支 A（填 0）：如果我们在此位填 0，那么由于高位已经比 n 的 1 小了，后续的低 2 位（第 1 位和第 0 位）无论怎么填，整个数都必定小于 n！
  • 此时低 2 位可以自由组合，贡献的合法方案数为 dp[2] = 3（对应 000, 001, 010，即 0, 1, 2）。
• 分支 B（跟随填 1）：如果我们在此位跟随 n 填 1，说明我们暂时还“贴着上限”，需要继续看低位的决策。

第二步：扫描第 1 位（值为 0）

• 因为 n 在这一位是 0，我们为了不超过 n，只能跟随填 0。
• 这里无法分出一个“比 n 小且后续自由填”的分支，直接进入下一位。

第三步：扫描第 0 位（值为 1）

• 分支 A（填 0）：在此位填 0，前两位固定为 10，低 0 位自由填。
  • 贡献的合法方案数为 dp[0] = 1（对应 100，即 4）。
• 分支 B（跟随填 1）：跟随填 1，组合为 101（即 5 本身）。

扫描结束

如果全程没有触犯“连续 1”的规则，最后加上 n 本身（即 101），总答案为：

• res = dp[2] + dp[0] + 1 = 3 + 1 + 1 = 5

---

避坑指南：如果 n 本身就有连续 1 怎么办？

假设 n = 6，二进制为 1 1 0：

1. 第 2 位（1）：
   • 填 0 贡献 dp[2] = 3（数 0, 1, 2）。
   • 跟随填 1 当前高位为 1。
2. 第 1 位（1）：
   • 填 0 高位为 10，后面自由填，贡献 dp[1] = 2（数 4, 5）。
   • 跟随填 1 停！此时高位变为了 11！

由于高位出现了连续的 1，意味着任何“紧贴 n 并在后续跟随”的填法都必然非法！
因此，后方的所有分支全部失效，我们可以直接提前 Return 终止循环！

---

05. 完整 Java 代码实现

结合上面的推导逻辑，代码写起来非常简洁清晰：

public class Solution {
    public int findIntegers(int n) {
        // 1. 预处理 dp 数组：dp[i] 表示长度为 i 的二进制串中无连续 1 的合法方案数
        int[] dp = new int[31];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < 31; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        int res = 0;
        int preBit = 0; // 记录上一位的二进制值（0 或 1）

        // 2. 从最高位（第 29 位，因为 10^9 < 2^30）开始逐位扫描
        for (int i = 29; i >= 0; i--) {
            int val = (1 << i);

            // 当前位是 1
            if ((n & val) != 0) {
                // 分支 1：当前位填 0，后面的 i 位可以自由组合
                res += dp[i];

                // 分支 2：当前位跟随填 1，检查是否与上一位构成连续 1
                if (preBit == 1) {
                    // 出现了连续 1，后续跟随分支全部无效，提前返回
                    return res;
                }
                preBit = 1;
            } else {
                // 当前位是 0，只能跟随填 0
                preBit = 0;
            }
        }

        // 3. 如果 n 本身不包含连续 1，加上 n 这个数本身
        return res + 1;
    }
}

复杂度分析

• 时间复杂度：O(log n)。我们只需要预处理 30 个位置的 dp 值，并从最高位到低位循环 30 次，耗时在毫秒级以内！
• 空间复杂度：O(1)。仅需常数级别的 dp 数组与状态变量。

---

总结与认知提升

做完这道题，我们可以总结出解决“数位 DP”类问题的标准套路：

1. 脱离限制找规律：先不考虑上限 n，用 DP 预处理出“无限制下长度为 i 的合法方案数”。
2. 高位切分树状分支：从高位到低位遍历 $n$ 的每一位。遇到 1 时拆分为两个分支——填 0 自由组合 vs 跟随填 1 继续向下。
3. 及时剪枝：一旦跟随分支触发了非法条件（如出现连续 1），后面的树枝全部砍掉，直接结束。

算法并不是冰冷的公式堆砌，每一个 DP 状态背后都是对求解空间的精妙拆分。下次再遇到类似的“统计 [0, n] 范围内满足某种特征的数字个数”时，不妨试着用这种“高位试填”的视角去思考吧！

欢迎关注个人公众号