C++で少なくとも3つの連続した1を持つ長さNのバイナリ文字列の数を見つけます

整数Nがあると仮定します。少なくとも、3つの連続した1を持つ、長さNのすべての可能な個別のバイナリ文字列の数を見つける必要があります。したがって、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 =0の（i – 1）番目の位置の値
• i番目のインデックスに1がある場合、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