บทเรียน: Dynamic Programming

Dynamic Programming (DP) ใช้เมื่อปัญหาแตกเป็นปัญหาย่อยที่ซ้ำกัน (overlapping subproblems) วิธีคือเก็บผลลัพธ์ย่อยไว้ใช้ซ้ำ (memoization) ไม่ต้องคำนวณใหม่ เคล็ดลับคือเริ่มจากเขียน recursion ปกติก่อน แล้วค่อยเพิ่ม cache

Fibonacci — เห็นความซ้ำชัดที่สุด

# แบบช้า: คำนวณซ้ำมหาศาล O(2^n)
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

# แบบ DP: จำผลลัพธ์ไว้ O(n)
def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(30))  # 832040 (เร็วมาก)

2 แนวทางของ DP

• Top-down (memoization) — เขียน recursion แล้วเก็บผลลัพธ์ใน dict/array
• Bottom-up (tabulation) — สร้างตารางแล้วไล่เติมจากเล็กไปใหญ่