如何计算n位二进制数中连续0个数≤4的组合总数？

核心思路：动态规划递推 #

直接枚举n较大的情况效率极低，用动态规划拆分状态是最优解。我们通过定义不同结尾状态的组合数，逐步推导总数：

状态定义

设：

• dp[i][0]：长度为i的二进制字符串中，最后一位是1（即结尾连续0个数为0）且所有位置连续0不超过4的组合数
• dp[i][1]：长度为i的二进制字符串中，结尾恰好有1个连续0且所有位置连续0不超过4的组合数
• dp[i][2]：结尾恰好有2个连续0的符合条件组合数
• dp[i][3]：结尾恰好有3个连续0的符合条件组合数
• dp[i][4]：结尾恰好有4个连续0的符合条件组合数

递推公式

基于前i-1位的状态，推导第i位的状态：

• dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4]
  解释：不管前i-1位结尾有几个连续0，只要在最后加一个1，就会形成结尾为1的新组合
• dp[i][1] = dp[i-1][0]
  解释：只有前i-1位结尾是1时，加一个0才会形成结尾恰好1个连续0的组合
• dp[i][2] = dp[i-1][1]
  解释：前i-1位结尾恰好1个连续0，加一个0就变成2个连续0
• dp[i][3] = dp[i-1][2]
• dp[i][4] = dp[i-1][3]

初始条件（i=1时）

长度为1的二进制字符串只有"0"和"1"：

• dp[1][0] = 1（对应"1"）
• dp[1][1] = 1（对应"0"）
• dp[1][2] = 0
• dp[1][3] = 0
• dp[1][4] = 0
  此时总数为 dp[1][0]+dp[1][1]+dp[1][2]+dp[1][3]+dp[1][4] = 2，符合预期。

计算总数

对于长度为n的二进制字符串，符合条件的总数为：
S(n) = dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4]

示例验证 #

以n=5为例：

• i=2：dp[2][0]=2，dp[2][1]=1，dp[2][2]=1，其余为0，总数=4
• i=3：dp[3][0]=4，dp[3][1]=2，dp[3][2]=1，dp[3][3]=1，总数=8
• i=4：dp[4][0]=8，dp[4][1]=4，dp[4][2]=2，dp[4][3]=1，dp[4][4]=1，总数=16
• i=5：dp[5][0]=16，dp[5][1]=8，dp[5][2]=4，dp[5][3]=2，dp[5][4]=1，总数=31
  这与实际情况一致：5位二进制总共有32种组合，只有"00000"不符合，所以符合条件的是31种。

特殊情况：最高位为1的n位二进制数 #

如果题目中的"n位二进制数"指的是最高位不能为0（即数值范围从2^(n-1)到2^n-1），只需在总数中减去以0开头的符合条件的组合数即可。以0开头的组合等价于长度为n-1的符合条件的二进制字符串，所以最终结果为：
S(n) - S(n-1)

比如n=2时，最高位为1的二进制数是"10"、"11"，共2种。用公式计算：S(2)-S(1)=4-2=2，正确。

内容的提问来源于stack exchange，提问作者Ryan Larson