หาเลข Catalan ลำดับที่ n ใน Python

Catalan Numbers: ลำดับจำนวนธรรมชาตินิยามด้วยสูตรเวียนเกิด

c₀ = 1, cₙ₊₁ = Σ cᵢ cₙ₋ᵢ₋₁ (i=0..n) สำหรับ n ≥ 0

ค่าแรกๆ: 1, 1, 2, 5, 14, 42, 132, 429...

วิธี 1: Recursion

def catalan(n):
    if n <= 1:
        return 1
    res = 0
    for i in range(n):
        res += catalan(i) * catalan(n-i-1)
    return res

for i in range(6):
    print(catalan(i))

ผลลัพธ์

1 1 2 5 14 42

วิธี 2: Dynamic Programming

def catalan(n):
    if n == 0 or n == 1:
        return 1
    catalan_arr = [0] * (n + 1)
    catalan_arr[0] = catalan_arr[1] = 1
    for i in range(2, n + 1):
        catalan_arr[i] = 0
        for j in range(i):
            catalan_arr[i] += catalan_arr[j] * catalan_arr[i-j-1]
    return catalan_arr[n]

for i in range(6):
    print(catalan(i), end=" ")

ผลลัพธ์

1 1 2 5 14 42

สรุป

เรียนรู้ 2 วิธีสร้างเลข Catalan ลำดับที่ n: Recursion และ Dynamic Programming (Bottom-up)