C++에서 최소 3개의 연속 1이 있는 길이가 N인 이진 문자열의 수를 찾으십시오.

정수 N이 있다고 가정하고 길이가 N이고 연속 1이 3개 이상 있는 가능한 모든 고유한 이진 문자열의 수를 찾아야 합니다. 따라서 n =4이면 숫자는 0111, 1110, 1111이 되므로 출력은 3이 됩니다.

이를 해결하기 위해 동적 프로그래밍 접근 방식을 사용할 수 있습니다. 따라서 DP(i, x)는 i + 1에서 i + x 위치에 x 연속 1이 있는 길이 i의 문자열 수를 나타냅니다. 그러면 반복 관계는 다음과 같습니다. -

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