Module 1 — Tổng kết & cheat sheet
Recap DP/Greedy/Backtracking: bảng quyết định khi nào dùng công cụ nào, glossary 13 thuật ngữ, 5 pitfall tổng hợp, self-assessment 4 outcomes và tài liệu mở rộng.
TL;DR: Module 1 trang bị tam giác quyết định tối ưu — DP khi subproblem trùng lặp và cần optimal substructure, Greedy khi chứng minh được greedy-choice property, Backtracking khi cần enumerate tất cả nghiệm với cắt tỉa. Trang này là cheat sheet để bookmark: bảng khi nào dùng gì, glossary 13 thuật ngữ cốt lõi, 5 pitfall hay gặp nhất và self-assessment 4 câu. Nếu bạn giải thích được tại sao coin change dùng DP mà interval scheduling dùng greedy, và design được backtracking cho N-queens với pruning, bạn đã sẵn sàng cho Module 2.
Đã đi qua những gì
Bạn bắt đầu từ bài 00 — Tổng quan module: ba kỹ thuật có quan hệ với nhau theo tam giác quyết định — DP mạnh nhất nhưng tốn nhất, Greedy nhanh nhất nhưng cần chứng minh, Backtracking toàn diện nhất nhưng mũ.
Bài 01 — DP Framework đặt nền móng: hai điều kiện (overlapping subproblems + optimal substructure), hai cách implement (memoization top-down vs tabulation bottom-up), và quy trình 5 bước xác định state → transition → base case → thứ tự tính → tối ưu space. Fibonacci từ O(2ⁿ) xuống O(1) là bài minh hoạ.
Bài 02 — DP 1D Patterns áp framework vào bốn pattern kinh điển: climbing stairs (đếm cách leo bậc), house robber (max không kề nhau), Kadane (max subarray liên tiếp), coin change (số xu ít nhất). Bốn pattern này xuất hiện như sub-bài trong phần lớn bài medium Leetcode.
Bài 03 — DP 2D: LCS và Edit Distance mở rộng state lên hai chiều. Bảng dp[i][j] — một ô cho mỗi cặp prefix — là cấu trúc chung. LCS đếm độ dài chung; Edit Distance đếm thao tác insert/delete/replace để biến chuỗi này thành chuỗi kia.
Bài 04 — Knapsack là bài toán tối ưu hoá có ràng buộc trọng lượng: chọn items sao cho tổng giá trị tối đa trong giới hạn W. State dp[i][w] — xét i items đầu với capacity w còn lại. Knapsack 0/1 không thể giải bằng greedy vì items không chia được.
Bài 05 — Greedy dạy khi nào lựa chọn cục bộ tốt nhất dẫn đến tối ưu toàn cục. Greedy choice property và optimal substructure là hai điều kiện bắt buộc. Exchange argument là phương pháp chứng minh chuẩn: giả sử OPT khác greedy → hoán đổi phần tử → OPT không tệ hơn → mâu thuẫn. Interval scheduling (sort theo finish time) và Huffman coding (gộp hai node min-frequency) là hai ví dụ greedy đúng hoàn toàn.
Bài 06 — Backtracking khép lại tam giác với khung choose → explore → unchoose. Tại mỗi bước chọn một lựa chọn, đệ quy xuống, hoàn tác để thử lựa chọn khác. Pruning (cắt tỉa sớm khi constraint đã bị vi phạm) là sự khác biệt giữa backtracking thực tế và brute force mũ. N-queens, permutations và subsets đều dùng cùng một khung.
Bài 07 — Mini-challenge cho bạn tự implement Edit Distance từ đầu: đọc đề, thiết kế bảng dp, viết transition, kiểm tra với test case. Cầu nối quan trọng từ hiểu lý thuyết sang tự làm độc lập.
Bài 08 — Case study cho thấy bạn đã biết tất cả để hiểu hai công cụ production: git diff chạy Myers algorithm (variant của LCS) để tìm minimal edit script hiển thị dấu +/-, và gzip (DEFLATE) chạy Huffman coding để gán mã bit ngắn hơn cho ký tự xuất hiện nhiều.
🗺️ Cheat sheet
Khi nào dùng công cụ nào
graph TD
PROB["Bài toán tối ưu\nhoặc tổ hợp"] --> Q1{"Subproblem\ntrùng lặp?"}
Q1 -- "Có" --> Q2{"Greedy choice\nchứng minh được?"}
Q2 -- "Có" --> GREEDY["Greedy\nO(n log n)"]
Q2 -- "Không" --> DP["DP\nO(n²) hoặc O(n·W)"]
Q1 -- "Không" --> Q3{"Cần tất cả\nnghiệm?"}
Q3 -- "Có" --> BT["Backtracking + Pruning\nO(n!) worst case"]
Q3 -- "Không" --> DC["Divide & Conquer"]Bảng so sánh ba kỹ thuật
| Tiêu chí | DP | Greedy | Backtracking |
|---|---|---|---|
| Khi nào dùng | Overlapping subproblems + optimal substructure | Greedy choice property chứng minh được | Cần enumerate nghiệm với constraint |
| Complexity time | O(n²), O(n×W), O(mn) thường gặp | O(n log n) thường gặp | O(n!), O(2ⁿ) worst case |
| Complexity space | O(n), O(mn), tối ưu xuống O(n) | O(n) thường gặp | O(depth) call stack |
| Đảm bảo tối ưu | Có | Có (khi chứng minh được) | Có (tìm mọi nghiệm) |
| Pitfall | Sai state, sai thứ tự, quên base case | Dùng mà không chứng minh | Không pruning → quá chậm |
| Ví dụ kinh điển | Knapsack, LCS, Edit Distance, Coin change | Interval scheduling, Huffman, Fractional knapsack | N-queens, Permutations, Subsets, Sudoku |
Khi greedy ĐÚNG vs SAI
| Bài toán | Greedy | Lý do |
|---|---|---|
| Interval scheduling | Đúng (sort theo finish time) | Finish sớm nhất chiếm ít tương lai nhất — chứng minh exchange argument |
| Huffman coding | Đúng (gộp hai node min-freq) | Node min-freq luôn ở depth lớn nhất trong cây tối ưu |
| Fractional knapsack | Đúng (ratio value/weight giảm dần) | Items chia được — ratio tốt nhất không chặn kết hợp |
| 0/1 Knapsack | SAI | Items không chia — greedy chọn item lớn có thể chặn kết hợp tốt hơn |
| Coin change (mệnh giá lạ) | SAI | Mệnh giá {1, 3, 4}: greedy chọn 4 phá tổ hợp {3, 3} tốt hơn |
| Dijkstra (không có edge âm) | Đúng | Greedy invariant: dist min đã finalized không thể cải thiện |
| Dijkstra (có edge âm) | SAI | Edge âm phá greedy invariant |
DP — Pattern nhanh nhận dạng
| Dấu hiệu trong đề | Pattern khả năng | State gợi ý |
|---|---|---|
| "Số cách" hoặc "ít nhất N bước" trên dãy | DP 1D | dp[i] = kết quả tới vị trí i |
| "Max/min trên dãy con liên tiếp" | Kadane variant | dp[i] = kết quả kết thúc tại i |
| "Hai chuỗi, tìm chung/biến đổi" | DP 2D | dp[i][j] = kết quả với prefix i và j |
| "Chọn items với ràng buộc tổng" | Knapsack variant | dp[i][w] = tối ưu với i items, capacity w |
| "Tất cả hoán vị/tập con" | Backtracking | Cây quyết định choose/explore/unchoose |
| "Chứng minh được lựa chọn tham lam" | Greedy | Exchange argument |
📖 Glossary
| Thuật ngữ | Định nghĩa 1 câu |
|---|---|
| Overlapping subproblems | Tính chất bài toán: cùng subproblem nhỏ xuất hiện nhiều lần trong quá trình giải bài lớn — điều kiện cần của DP. |
| Optimal substructure | Tính chất bài toán: nghiệm tối ưu của bài lớn được xây từ nghiệm tối ưu của các subproblem — điều kiện cần của cả DP lẫn greedy. |
| Memoization | Implement DP top-down: giữ nguyên cấu trúc đệ quy, thêm bảng cache trước mỗi lần tính — lazy, chỉ tính subproblem thực sự được gọi. |
| Tabulation | Implement DP bottom-up: vòng lặp điền bảng từ base case lên — eager, không có stack overflow risk, dễ tối ưu space. |
| State (DP) | Tham số đủ để xác định kết quả của một subproblem mà không cần biết lịch sử đã đến state đó như thế nào (tính chất Markov). |
| Transition | Công thức tính dp[state] từ các state nhỏ hơn đã được giải — cốt lõi của thuật toán DP. |
| Base case | Subproblem nhỏ nhất có thể trả lời trực tiếp không cần chia nhỏ hơn — điểm dừng đệ quy hoặc điểm khởi đầu tabulation. |
| Greedy choice property | Lựa chọn tham lam tại bước đầu tiên là thành phần của ít nhất một nghiệm tối ưu toàn cục — điều kiện đặc trưng của greedy (mạnh hơn optimal substructure). |
| Exchange argument | Kỹ thuật chứng minh greedy: giả sử OPT khác greedy tại bước nào đó, hoán đổi phần tử OPT thành lựa chọn greedy, chứng minh nghiệm mới không tệ hơn. |
| Pruning | Cắt tỉa sớm trong backtracking: khi trạng thái hiện tại đã vi phạm constraint, dừng đệ quy ngay thay vì tiếp tục xuống sâu hơn. |
| Choose–Explore–Unchoose | Ba bước khung backtracking: chọn một lựa chọn, đệ quy xuống, hoàn tác lựa chọn để thử lựa chọn khác. |
| LCS | Longest Common Subsequence — dãy con chung dài nhất của hai chuỗi, không cần liên tiếp. Nền tảng của git diff và sequence alignment. |
| Edit Distance | Số thao tác insert/delete/replace ít nhất để biến chuỗi A thành chuỗi B (Levenshtein distance). Dùng trong spell checker, DNA comparison, fuzzy search. |
⚠️ Pitfall tổng hợp
Pitfall 1 — Dùng greedy mà không chứng minh.
Greedy "trông có vẻ đúng" là bẫy phổ biến nhất. Coin change với mệnh giá {1, 3, 4} và amount = 6: greedy chọn 4 → còn 2 → cần 2 đồng 1 → tổng 3 đồng. DP tìm được 3 + 3 = 2 đồng. Trước khi dùng greedy, luôn hỏi: "Tôi có thể chứng minh greedy choice property bằng exchange argument không?" Không chứng minh được → dùng DP.
Pitfall 2 — State DP thiếu chiều — kết quả sai im lặng.
Bài robot đi grid có ràng buộc "đã dùng k bước đặc biệt": nếu state chỉ là (i, j), hai tình huống khác nhau (dùng 0 bước đặc biệt vs dùng 1 bước) bị merge vào cùng cell dp[i][j] → kết quả sai. Khi gặp kết quả lạ trong DP, câu hỏi đầu tiên là: "State có đủ thông tin để xác định kết quả mà không cần biết lịch sử không?" Nếu chưa → thêm chiều vào state.
Pitfall 3 — Sai thứ tự tabulation.
Tabulation yêu cầu khi tính dp[i], tất cả state nó phụ thuộc phải đã sẵn sàng. Coin change unbounded: vòng lặp ngoài phải là amount (tăng dần), vòng trong là coins — không phải ngược lại. Edit Distance: phải điền hàng trên trước hàng dưới, cột trái trước cột phải. Vẽ bảng tay và xác định dependency trước khi code.
Pitfall 4 — Backtracking không pruning, chạy mãi không xong. N-queens với n = 15 mà không pruning: 15! ≈ 1.3 × 10¹² node — không thể chạy hết. Pruning kiểm tra constraint sớm nhất có thể: với N-queens, kiểm tra row/column/diagonal conflict ngay khi đặt queen, trước khi đệ quy xuống. Nguyên tắc: cắt tỉa càng sớm càng cao trong cây → loại bỏ nhiều nhánh nhất.
Pitfall 5 — Nhầm Backtracking với DP khi bài hỏi "đếm số cách". "Đếm số cách" có thể là DP (nếu subproblem trùng lặp và không cần liệt kê từng cách) hoặc Backtracking (nếu cần liệt kê cụ thể từng cách). Coin change "tìm số xu ít nhất" là DP. "Liệt kê tất cả cách đổi" là Backtracking. Hỏi: "Đề yêu cầu đếm hay liệt kê?" — câu trả lời quyết định công cụ.
✅ Self-assessment
Bạn đã đạt module này nếu trả lời được:
- Giải thích được hai điều kiện áp dụng DP (overlapping subproblems + optimal substructure) và phân biệt memoization với tabulation — khi nào top-down, khi nào bottom-up, trade-off stack depth và space.
- Nếu chưa: đọc lại bài 01 — DP Framework mục 2 (hai điều kiện) và mục 3 (so sánh memoization vs tabulation).
- Implement được DP 1D/2D và knapsack — thiết kế state, transition, base case cho bài toán mới theo quy trình 5 bước mà không cần gợi ý.
- Nếu chưa: làm lại bài 07 — Mini-challenge từ đầu không đọc solution; xem lại bài 03 — DP 2D mục bảng transition.
- Justify được tính đúng của greedy bằng greedy-choice property và exchange argument, và đưa ra counter-example khi greedy SAI (coin change mệnh giá lạ, 0/1 knapsack).
- Nếu chưa: đọc lại bài 05 — Greedy mục 3 (exchange argument) và mục 6 (khi nào greedy SAI).
- Design được backtracking với pruning cho bài tổ hợp — vẽ được cây quyết định, xác định điểm cắt tỉa, phân tích complexity với và không có pruning.
- Nếu chưa: đọc lại bài 06 — Backtracking mục 2 (khung tổng quát) và mục N-queens với bảng phân tích pruning.
🚀 What's next
Module 1 trang bị ba công cụ quyết định tối ưu — từ nền tảng DP đến greedy có chứng minh đến backtracking với pruning. Module 2 — Pattern matching & String đưa những kỹ thuật này vào một domain cụ thể: bài toán trên chuỗi ký tự. KMP (Knuth-Morris-Pratt) và Rabin-Karp là hai thuật toán string search không phải brute force O(nm); suffix array và suffix tree là cấu trúc dữ liệu cho bài toán so khớp nhiều pattern cùng lúc. Module 2 cũng xây thẳng trên LCS và Edit Distance từ bài 03 và 07 của module này.
Bài tiếp theo: Module 2 — Pattern matching & String
(Module 2 đang được phát triển.)
📚 Tài liệu mở rộng
- Introduction to Algorithms (CLRS, 4th ed. 2022), Chapters 14-15: Chương 14 — Dynamic Programming (rod cutting, matrix chain, LCS, optimal BST) với proof đầy đủ về optimal substructure và overlapping subproblems. Chương 15 — Greedy Algorithms (activity selection, Huffman, §15.4 Matroids): lý thuyết matroid giải thích tại sao greedy đúng trên weighted matroid, bao gồm Kruskal MST.
- Algorithm Design (Kleinberg & Tardos), Chapters 6-7: Tiếp cận từ bài toán thực tế: weighted interval scheduling (DP), sequence alignment (edit distance ứng dụng sinh học), Bellman-Ford và network flow. Chương 7 về network flow dùng nhiều tư duy DP và greedy.
- Competitive Programmer's Handbook (Laaksonen) — Chapters 5-7: Tài liệu miễn phí, bao gồm DP patterns, knapsack variants, và backtracking cho competitive programming. Nhiều bài tập với giải thích ngắn gọn.
- LeetCode patterns — neetcode.io: Danh sách 150 bài Leetcode theo pattern (DP 1D, DP 2D, knapsack, backtracking). Sau khi học xong module, luyện theo danh sách này để củng cố nhận dạng pattern.
- Huffman (1952) — "A Method for the Construction of Minimum-Redundancy Codes": Bài báo gốc 4 trang — David Huffman viết như bài tập cuối kỳ tại MIT thay vì thi. Readable và ngắn gọn.
Bài này có giúp bạn hiểu bản chất không?
Hỏi đáp về bài này
Chưa có câu hỏi
Có gì chưa rõ trong bài? Đặt câu hỏi đầu tiên — câu trả lời từ cộng đồng giúp bạn (và người sau).
Đặt câu hỏi đầu tiên