Giao diện
Dynamic Programming — Quy hoạch động 🧠
Khi một hệ thống recommendation engine xử lý hàng triệu user-item pairs mỗi giây, hay khi GPS tính toán tuyến đường tối ưu qua hàng nghìn nút giao — đằng sau đó là Dynamic Programming. Đây không chỉ là kỹ thuật giải bài interview, mà là nền tảng tư duy tối ưu hóa mà mọi kỹ sư phần mềm cần nắm vững.
Lộ trình học
Nội dung DP trong Penalgo được thiết kế theo trình tự tăng dần. Bắt đầu từ bài toán kinh điển nhất, mỗi bài xây dựng trên nền kiến thức của bài trước.
Foundation Intermediate Advanced
│ │ │
▼ ▼ ▼
Climbing Stairs → 0/1 Knapsack → LCS ────→ Bitmask DP
(Fibonacci) (Tối ưu lựa (String (Tối ưu
chọn + ràng DP, diff tổ hợp,
buộc) algorithm) TSP)Khuyến nghị: Hoàn thành từng bài theo thứ tự. Mỗi bài giới thiệu pattern mới và xây dựng trên kỹ thuật đã học.
Nội dung
🟢 Foundation
| Bài học | Thời gian | Nội dung chính |
|---|---|---|
| Climbing Stairs | 25 phút | Gateway vào DP, kết nối Fibonacci, tối ưu O(n) → O(1) |
🟡 Intermediate
| Bài học | Thời gian | Nội dung chính |
|---|---|---|
| 0/1 Knapsack | 35 phút | Tối ưu hóa lựa chọn với constraint, 2D→1D optimization |
| Longest Common Subsequence | 35 phút | String DP, diff algorithm, edit distance connection |
🔴 Advanced
| Bài học | Thời gian | Nội dung chính |
|---|---|---|
| Bitmask DP | 45 phút | DP trên tập con, TSP, Gosper's hack, subset enumeration |
Kiến thức nền tảng
Trước khi bắt đầu, hãy đảm bảo bạn hiểu rõ hai điều kiện tiên quyết của DP:
Overlapping Subproblems — Bài toán con được gọi lặp đi lặp lại. Thay vì tính lại, ta lưu trữ kết quả.
Optimal Substructure — Nghiệm tối ưu của bài toán lớn có thể xây dựng từ nghiệm tối ưu của bài toán con.
Hai tiếp cận chính: Top-Down (đệ quy + memoization) và Bottom-Up (vòng lặp + tabulation). Mỗi bài học sẽ triển khai cả hai, sau đó tối ưu hóa space.
🧠 Quiz
Câu 1: Bài Climbing Stairs là ví dụ kinh điển nhất cho DP vì lý do gì?
- [ ] A) Vì nó khó nhất trong các bài DP
- [x] B) Vì nó minh họa rõ ràng overlapping subproblems: climb(n) = climb(n-1) + climb(n-2), giống Fibonacci
- [ ] C) Vì nó là bài duy nhất có thể giải bằng DP
- [ ] D) Vì nó yêu cầu Bitmask DP
💡 Giải thích: Climbing Stairs: số cách lên bậc n = cách lên bậc n-1 (bước 1 bậc) + cách lên bậc n-2 (bước 2 bậc). Đệ quy thuần → O(2ⁿ). Thêm memo → O(n). Bottom-up → O(n) time, O(1) space. Trình diễn hoàn hảo lý do DP hiệu quả.
Câu 2: Knapsack 0/1 khác gì Unbounded Knapsack?
- [ ] A) Không có sự khác biệt
- [x] B) 0/1: mỗi vật chỉ chọn tối đa 1 lần. Unbounded: mỗi vật chọn không giới hạn số lần
- [ ] C) 0/1 chỉ có 2 vật, Unbounded có nhiều vật
- [ ] D) 0/1 dùng Greedy, Unbounded dùng DP
💡 Giải thích: 0/1 Knapsack: dp[i][w] xét vật i — lấy hoặc không → dùng mảng 2D. Unbounded: dp[w] vì mỗi vật có thể lấy nhiều lần → duyệt w từ nhỏ đến lớn. Greedy KHÔNG cho kết quả tối ưu với 0/1 Knapsack (cần DP).
→ Bắt đầu với Climbing Stairs — Bài toán gateway vào DP