在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