สมมติว่า เรามีจำนวนเต็ม N เราต้องหาจำนวนสตริงไบนารีที่เป็นไปได้ทั้งหมดที่เป็นไปได้ของความยาว N ซึ่งมี 1 วินาทีติดต่อกันเป็นอย่างน้อย ดังนั้นถ้า n =4 ตัวเลขจะเป็น 0111, 1110, 1111 ดังนั้นผลลัพธ์จะเป็น 3
เพื่อแก้ปัญหานี้ เราสามารถใช้วิธีการเขียนโปรแกรมไดนามิก ดังนั้น DP(i, x) จึงระบุจำนวนสตริงที่มีความยาว i โดยที่ x ต่อเนื่องกัน 1 วินาทีในตำแหน่ง i + 1 ถึง i + x จากนั้นความสัมพันธ์การเกิดซ้ำจะเป็นเช่น −
DP(i, x) =DP(i – 1, 0) + DP(i – 1, x + 1).
การเกิดซ้ำขึ้นอยู่กับข้อเท็จจริงที่ว่าสตริงสามารถมี 0 หรือ 1 อยู่ที่ตำแหน่ง i
- ถ้ามี 0 ที่ดัชนี ith สำหรับ (i – 1) ค่าตำแหน่งที่ x =0
- ถ้ามี 1 ที่ดัชนี ith สำหรับ (i – 1) ค่าตำแหน่งที่ x =1 + ค่าของ x ที่ตำแหน่ง i
ตัวอย่าง
#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
