Lesson 23 — Quy hoạch động: Nền tảng

DP = đệ quy + nhớ. Ba module dưới đây minh họa: (1) vì sao overlap làm naive nổ mũ và memo cứu thế nào; (2) hai cách điền bảng top-down vs bottom-up; (3) khung thiết kế DP 5 bước qua bài climbing stairs.

1. Cây gọi Fibonacci — overlap vs cache

n (3–7)

lời gọi: – state phân biệt: –

Chọn chế độ rồi bấm "Vẽ cây".

2. Top-down vs Bottom-up — điền bảng dp

n (2–10)

dp[i] = số cách leo i bậc (Fibonacci). chế độ: top-down

Bấm "Chạy từng bước".

3. Thiết kế DP 5 bước — Climbing Stairs

bước 0 / 5

Bước 1 — Định nghĩa STATE

dp[i] = số cách leo lên đúng bậc i. State là một câu rõ ràng — đây là nền móng, sai từ đây là sai hết.

Bước 2 — RECURRENCE (transition)

Bước cuối để tới bậc i: hoặc từ i-1 (bước 1 bậc) hoặc từ i-2 (bước 2 bậc). ⟹ dp[i] = dp[i-1] + dp[i-2].

Bước 3 — BASE CASE

dp[0] = 1 (1 cách "không làm gì"), dp[1] = 1. ⚠ Đặt dp[0]=0 là sai — sẽ ra dp[2]=1 thay vì 2.

Bước 4 — THỨ TỰ TÍNH

dp[i] cần dp[i-1], dp[i-2] ⟹ điền từ i = 2 tăng dần tới n (topological order của dependency).

Bước 5 — ĐÁP ÁN

Kết quả nằm ở dp[n]. Vd n=5: dãy 1,1,2,3,5,8 ⟹ dp[5] = 8 cách.