在C ++中找到长度为N且至少连续3个1的二进制字符串数

假设我们有一个整数N，我们必须找到长度为N的所有可能的不同二进制字符串的数量，这些字符串至少具有三个连续的1。因此，如果n = 4，则数字将为0111、1110、1111，因此输出将为3。

为了解决这个问题，我们可以使用动态编程方法。因此DP(i,x)表示长度为i的字符串数，在位置i +1到i + x处有x个连续的1。那么递归关系将像-

DP(i,x)= DP（i – 1，0）+ DP（i – 1，x + 1）。

重复发生基于以下事实：字符串在位置i处可以有0或1。

• 如果它有0，则在第i个索引处，则x的第（i – 1）个位置值= 0

• 如果它有1，则在第i个索引处，则x的第（i – 1）个位置值= 1 +第i个位置的x值

示例

#include<iostream>
using namespace std;
int n;
int numberCount(int i, int x, int table[][4]) {
   if (i < 0)
      return x == 3;
   if (table[i][x] != -1)
      return table[i][x];
      table[i][x] = numberCount(i - 1, 0, table);
      table[i][x] += numberCount(i - 1, x + 1, table);
      return table[i][x];
   }
int main() {
   n = 4;
   int table[n][4];
   for (int i = 0; i < n; i++)
   for (int j = 0; j < 4; j++)
      table[i][j] = -1;
   for (int i = 0; i < n; i++) {
      table[i][3] = (1 << (i + 1));
   }
   cout << "The number of binary strings with at least 3 consecutive 1s: " << numberCount(n - 1, 0, table);
}

输出结果

The number of binary strings with at least 3 consecutive 1s: 3