Cho N, đếm số chuỗi nhị phân độ dài N có ít nhất 3 số 1 liên tiếp. Ví dụ n=4 → 3 chuỗi: 0111, 1110, 1111.
Dùng quy hoạch động: DP(i, x) = số chuỗi độ dài i có x số 1 liên tiếp ở cuối. Quan hệ: DP(i, x) = DP(i-1, 0) + DP(i-1, x+1).
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); }
Kết quả
The number of binary strings with at least 3 consecutive 1s: 3