我们给定整数N和K。我们有长度为N的二进制字符串，仅包含0和1。目标是找到具有K个连续1的长度为N的此类字符串的数量。即，如果N = 3，而K = 2，则计算所有可能具有2个连续1的3位二进制字符串。
示例-111，此处相邻的1出现两次（K次）。
在011和110中，相邻的1仅出现一次。
我们将通过存储先前值的结果来解决此问题。
取3D数组count [x] [y] [z]。其中x为N，y为K，z为字符串的最后一位（0或1）
对于N = 1，字符串将为“ 0”和“ 1”。相邻1的计数= 0。
因此对于任何K。如果N = 1，则count = 0。
count [1] [K] [0] = count [1] [K] [1] = 0。
当最后一位数字为0时，将相邻1的计数计为K
长度为N-1的所有数字加上K个+最后0→新长度= N
如果与1相邻的K个计数为C，则最后加0不会更改该计数。
count [N] [K] [0] = count [N-1] [K] [0] + count [N-1] [K] [1]
当最后一位为1时，将相邻的1计数为K
长度为N-1的所有数字都以0结尾且K个+最后1个→新的长度= N，
计数[N-1] [K] [0]
长度为N-1的所有数字都以1结尾，K-1个数字+最后1→新的长度= N，
计数[N-1] [K-1] [1]
count [N] [K] [1] = count [N-1] [K] [0] + count [N-1] [K-1] [1]
这样的字符串总数= count [N] [K] [0] + count [N] [K] [1]
N=4, K=2
输出结果
Count of strings: 2
解释-1110、0111是唯一长度为4的字符串，其中相邻的1仅出现两次。
1110- “11 10”, then “1 11 0” ( splitting to show which adjacent 1’s are counted ) 0111- “0 11 1”, then “01 11”. K=2, adjacent 1’s= 2 times
N=3, K=1
输出结果
Count of strings: 2
解释-110，011.是唯一长度为3的字符串，其中相邻的1出现一次。
在111中，相邻的1出现两次。
整数N和K存储字符串的长度，否。每个中出现相邻1的时间。
函数stringcount（int n，int k）将n和k作为参数，并返回与K相邻的1的字符串数。
数组count [i] [j] [0/1]用于存储长度为i的字符串的计数，其中j相邻于1，以0或1结尾。
初始条件为count [1] [0] [0] = 1；count [1] [0] [1] = 1;
现在从2个长度的字符串（i = 2）到n个长度开始。对于每个这样的字符串，请检查相邻1的K次计数。j = 0; j <= k，来自先前的计数。更新当前计数[i] [j] [0]和计数[i] [j] [1]。
如果j-1> = 0，则相邻1的计数大于1。然后更新以1结尾的字符串的计数为count [i] [j] [1] + count [i-1] [j-1] [ 1];
最后添加count [n] [k] [0]和count [n] [k] [1]。结果将其存储。
返回结果作为所需的计数。
#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k){
//count of strings with length=n and adajcent 1's=k
int count[n + 1][k + 1][2]={0};
//count[n][k][0] -- strings with length=n and adajcent 1's=k last character is 0
//count[n][k][1] -- strings with length=n and adajcent 1's=k last character is 1
// If n = 1 and k = 0.
count[1][0][0] = 1;
count[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
// number of adjacent 1's can not exceed i-1
for (int j = 0; j <= k; j++) {
count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
count[i][j][1] = count[i - 1][j][0];
if (j - 1 >= 0)
count[i][j][1] =count[i][j][1] + count[i - 1][j - 1][1];
}
}
int result=count[n][k][0]+count[n][k][1];
return result;
}
int main(){
int N = 6, K = 3;
cout <<"Strings of length 6 and 3 adjacent 1's in each :"<< stringcount(N,K);
return 0;
}输出结果
Strings of length 6 and 3 adjacent 1's in each :7