การเขียนโปรแกรมแบบไดนามิก (memoization เทียบกับ tabulation) คืออะไร?

Question

Accepted Answer

**การเขียนโปรแกรมแบบไดนามิก (DP)** แก้ไขปัญหาที่มี **ปัญหาย่อยที่ทับซ้อน** และ **โครงสร้างที่เหมาะสม** โดยการคำนวณปัญหาย่อยแต่ละครั้งเพียงครั้งเดียวและนำผลลัพธ์กลับมาใช้ใหม่ สองรูปแบบคือ **memoization** (top-down) และ **tabulation** (bottom-up)

## แนวคิด

การวนซ้ำแบบไร้เดียงสาจะคำนวณปัญหาย่อยเดียวกันซ้ำแบบยกกำลัง DP จะจำไว้ โดยยุบงานแบบยกกำลังให้เป็นพหุนาม

## Memoization (top-down)

```python
from functools import lru_cache

@lru_cache(maxsize=None)               # cache results automatically
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)     # each n computed once
```

## Tabulation (bottom-up)

```python
def fib_table(n):
    if n < 2:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])  # build up from base cases
    return dp[n]
```

## Memoization เทียบกับ tabulation

| | Memoization | Tabulation |
|---|------------|------------||
| ทิศทาง | top-down recursion | bottom-up iteration |
| คำนวณ | เฉพาะสถานะที่ต้องการ | สถานะทั้งหมด |
| ความเสี่ยง | stack overflow | ไม่มี |
| พื้นที่ | สามารถตัดลด | มักจะลดลงเป็น O(1) แถว |

## ความซับซ้อน

ฟีโบนัชชี: จาก O(2ⁿ) ไร้เดียงสาเป็น **O(n)** เวลา O(n) (หรือ O(1)) พื้นที่

## เมื่อใด/ข้อเตือน

ใช้ DP เมื่อปัญหาย่อย **ทับซ้อน** กำหนดสถานะและการเกิดซ้ำอย่างระมัดระวัง — นั่นคือส่วนที่ยาก หากปัญหาย่อยไม่ทับซ้อน การแบ่งแยกและพิชิตแบบธรรมดาก็เพียงพอแล้ว

## เหตุใดจึงสำคัญ

DP เปลี่ยนปัญหาแบบยกกำลังที่แก้ไม่ได้ — เส้นทางที่สั้นที่สุด ระยะการแก้ไข เป้สะพายหลัง — ให้มีประสิทธิภาพ

ทักษะในการระบุสถานะและการเกิดซ้ำนับว่าเป็นสิ่งที่มีค่าที่สุดในสัมภาษณ์เกี่ยวกับอัลกอริทึม

เป็นพื้นฐานของระบบจริงจากเครื่องมือ diff ไปจนถึงการจัดตำแหน่งลำดับไบโออินฟอร์เมติกส์