Giả sử, chúng ta có một số nguyên N, Chúng ta phải tìm số tất cả các chuỗi nhị phân phân biệt có thể có độ dài N, mà có ít nhất ba số 1 liên tiếp. Vì vậy, nếu n =4, thì các số sẽ là 0111, 1110, 1111, do đó đầu ra sẽ là 3.
Để giải quyết vấn đề này, chúng ta có thể sử dụng cách tiếp cận Lập trình động. Vì vậy DP (i, x) cho biết số chuỗi có độ dài i với x 1s liên tiếp ở vị trí i + 1 đến i + x. Khi đó, mối quan hệ lặp lại sẽ giống như -
DP (i, x) =DP (i - 1, 0) + DP (i - 1, x + 1).
Việc lặp lại dựa trên thực tế là chuỗi có thể có 0 hoặc 1 ở vị trí i.
- Nếu nó có 0, ở chỉ số thứ i thì giá trị vị trí thứ (i - 1) của x =0
- Nếu nó có 1, ở chỉ số thứ i thì cho (i - 1) giá trị vị trí thứ của x =1 + giá trị của x ở vị trí thứ i
Ví dụ
#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);
} Đầu ra
The number of binary strings with at least 3 consecutive 1s: 3