如何优化统计含连续三个1的二进制序列组合数的算法？（Python/伪代码）

架构老林

2026-7-24

优化含三个连续1的二进制序列计数问题

原代码采用暴力枚举所有2^n种可能的方式，时间复杂度为O(2^n)，当n>30时，2^30已超过10亿，计算量直接爆炸。我们可以通过反向计算+递推公式将时间复杂度降到O(n)，甚至可进一步优化到O(logn)。

核心思路

直接统计包含三个连续1的组合数较繁琐，转换思路后更简单：

符合条件的组合数 = 总组合数 - 没有三个连续1的组合数

总组合数为2^n（每个位置有0/1两种选择）。关键是高效计算长度为n的二进制序列中，无三个连续1的组合数，记为f(n)。

递推关系推导

对f(n)，从序列末尾的三种合法情况分析：

最后一位是0：前n-1位满足无三个连续1即可，数量为f(n-1)
最后一位是1且倒数第二位是0：前n-2位满足条件即可，数量为f(n-2)
最后两位是11且倒数第三位是0：前n-3位满足条件即可，数量为f(n-3)

由此得到递推公式：
f(n) = f(n-1) + f(n-2) + f(n-3)

初始条件：

f(1) = 2（序列：0, 1）
f(2) = 4（序列：00, 01, 10, 11）
f(3) = 7（排除111，剩余7种）

优化后的代码实现

def count_combinations(n):
    if n < 3:
        return 0  # 长度小于3不可能存在三个连续1
    # 初始化递推的前三个值
    f_prev3, f_prev2, f_prev1 = 2, 4, 7
    if n == 3:
        return 2**3 - f_prev1
    # 递推计算f(n)
    for _ in range(4, n+1):
        f_current = f_prev3 + f_prev2 + f_prev1
        f_prev3, f_prev2, f_prev1 = f_prev2, f_prev1, f_current
    total = 2 ** n
    return total - f_prev1