Dynamic Programming เบื้องต้น

Dynamic Programming (DP) คือเทคนิคแก้ปัญหาที่ "ปัญหาย่อยซ้ำกัน" โดยจำผลที่คำนวณแล้วไว้ ไม่คำนวณซ้ำ ฟังดูยากแต่หัวใจง่ายมาก — และคุณเจอแนวคิดนี้มาแล้วในรูป @lru_cache (บท 3)

ปัญหา: fibonacci แบบ naive ช้าระเบิด

fib แบบ recursion ธรรมดาคำนวณ subproblem เดิมซ้ำเป็นล้านครั้ง — O(2^n)

def fib_slow(n):
    if n < 2:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)
# fib_slow(40) ช้ามาก — คำนวณ fib เดิมซ้ำมหาศาล

วิธีที่ 1: Memoization (top-down)

จำผลที่เคยคำนวณไว้ใน dict (หรือใช้ @lru_cache จากบท 3) — เจอแล้วหยิบเลย ไม่คำนวณซ้ำ → O(n)

import functools

@functools.lru_cache(maxsize=None)   # memoize อัตโนมัติ!
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(40))   # เร็วมาก (จำผลไว้แล้ว)

วิธีที่ 2: Tabulation (bottom-up)

สร้างคำตอบจากเล็กไปใหญ่ เก็บใน list/ตัวแปร — ไม่ใช้ recursion

def fib_tab(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b      # สร้างจากล่างขึ้นบน
    return b

print(fib_tab(40))   # เร็ว O(n) ใช้ memory คงที่

ตัวอย่าง: climbing stairs

ขึ้นบันได n ขั้น ก้าวได้ทีละ 1 หรือ 2 ขั้น มีกี่วิธี — เป็น fibonacci แฝง

def climb(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(n - 2):
        a, b = b, a + b
    return b

print(climb(5))   # 8 วิธี

สรุปหัวข้อนี้

• DP = ปัญหาย่อยซ้ำกัน → จำผลไว้ ไม่คำนวณซ้ำ
• memoization (top-down): recursion + cache (@lru_cache)
• tabulation (bottom-up): สร้างจากเล็กไปใหญ่ ไม่ใช้ recursion
• เริ่มจาก recursion ถูกก่อน แล้วเติม cache = ได้ DP