นับ Binary String ความยาว N ไม่มี 1 ติดกันใน Python

โจทย์: นับ Binary String ความยาว N ที่ไม่มี '11' (1 ติดกัน)

ตัวอย่าง

N = 5
Output: 13

อัลกอริทึม: Dynamic Programming (Fibonacci-like)

กำหนด: - a[i] = จำนวน string ความยาว i+1 ที่ลงท้ายด้วย 0 - b[i] = จำนวน string ความยาว i+1 ที่ลงท้ายด้วย 1

Recurrence: - a[i] = a[i-1] + b[i-1] (ต่อ 0 ได้จากทั้งคู่) - b[i] = a[i-1] (ต่อ 1 ได้แค่จากที่ลงท้าย 0)

Base: a[0] = b[0] = 1 (String ความยาว 1: "0", "1")
คำตอบ = a[n-1] + b[n-1] = F(n+2) (Fibonacci)

ตัวอย่างโค้ด Python

def count_binary_strings(n):
    if n == 0:
        return 0
    if n == 1:
        return 2  # "0", "1"
    
    a = [0] * n
    b = [0] * n
    a[0] = b[0] = 1
    
    for i in range(1, n):
        a[i] = a[i-1] + b[i-1]
        b[i] = a[i-1]
    
    return a[n-1] + b[n-1]

# ทดสอบ
print(count_binary_strings(5))  # 13

ผลลัพธ์

The number of strings: 13

ลำดับ Fibonacci

N: 1, 2, 3, 4, 5, 6, 7...
Count: 2, 3, 5, 8, 13, 21, 34... (F(n+2))

ความซับซ้อน: Time O(n), Space O(n) → ลดเป็น O(1) ได้ด้วย 2 ตัวแปร