Quyết định dưới constraint: tổng quan module

TL;DR: Module này dạy ba kỹ thuật để đưa ra quyết định tối ưu khi có ràng buộc (constraint): Dynamic Programming (DP) ghi nhớ kết quả của bài con (subproblem) để không phải tính lại, Greedy chọn phương án tốt nhất tại chỗ rồi chứng minh cách chọn đó đúng cho cả bài toán, Backtracking thử có hệ thống mọi nghiệm có thể và cắt tỉa sớm những nhánh không đi tới đâu. Đây là module đầu của tier 3 (thuật toán ứng dụng), nơi ba công cụ này có mặt hằng ngày trong production, qua git diff, gzip và các bộ giải Sudoku hay constraint solver.

Vì sao module này tồn tại

Mỗi lần bạn chạy git diff, thuật toán LCS (Longest Common Subsequence, một bài DP cổ điển) chạy ngầm để tìm các dòng chung dài nhất giữa hai phiên bản file. Mỗi lần bạn nén file thành .gz, Huffman coding (một thuật toán greedy) xây cây nhị phân tối ưu, gán mã bit ngắn hơn cho ký tự xuất hiện nhiều. Mỗi khi regex engine thử khớp một mẫu có nhánh rẽ, hay SAT solver (bộ giải bài toán thoả mãn logic) tìm nghiệm, backtracking và các biến thể của nó đang chạy bên dưới.

Khoá Thuật toán Cốt lõi đã cho bạn hộp đồ nghề: sorting, searching, graph traversal. Module này nâng lên một tầng khác: thay vì "tìm một đáp án", bài toán bây giờ là "tìm đáp án tốt nhất trong vô số lựa chọn". Đây là mảng của các bài Leetcode medium/hard, và cũng là mảng của nhiều bài toán engineering ngoài đời.

Ba kỹ thuật trong module có quan hệ với nhau theo một logic rõ ràng:

• DP mạnh nhất: dùng được cho mọi bài mà bài con lặp lại (overlapping subproblems) và đáp án bài lớn ghép được từ đáp án tối ưu của các bài con (optimal substructure), nhưng tốn O(n²) hoặc O(n×W) thời gian và bộ nhớ.
• Greedy nhanh nhất, thường O(n log n), nhưng chỉ đúng khi chứng minh được greedy choice property (chọn tốt nhất ở bước này không làm hỏng các bước sau). Không chứng minh được thì đừng dùng.
• Backtracking bao quát nhất, dùng được cho mọi bài tổ hợp, nhưng trường hợp xấu nhất lên tới O(n!) hoặc O(2ⁿ). Pruning (cắt nhánh sớm) giúp giảm thời gian chạy thực tế.

Biết cả ba, bạn có một tam giác quyết định: thử greedy trước, không chứng minh được thì chuyển sang DP, cần liệt kê nghiệm dưới ràng buộc phức tạp thì dùng backtracking.

Sau module này bạn sẽ

• Explain hai điều kiện áp dụng DP (overlapping subproblems + optimal substructure) và phân biệt memoization với tabulation
• Implement DP 1D/2D và knapsack — thiết kế state, transition, base case cho bài toán mới
• Justify tính đúng của greedy (exchange argument hoặc greedy stays ahead) và nhận ra khi nào greedy SAI
• Design backtracking với cắt tỉa (pruning) cho bài toán tổ hợp (hoán vị, tập con, N-queens)

Lộ trình module

Thứ tự bài và lý do

Bài 01: DP Framework là điểm khởi đầu vì mọi bài DP sau đều dùng cùng một khuôn: xác định state, viết transition, đặt base case, chọn thứ tự tính, nén bộ nhớ. Fibonacci là bài toán nhỏ nhất minh hoạ đủ cả năm bước: từ O(2ⁿ) bản naive xuống O(n) khi có memo, rồi xuống O(1) bộ nhớ.

Bài 02: DP 1D Patterns áp dụng framework ngay vào 4 pattern kinh điển trên mảng 1 chiều: climbing stairs (đếm cách), house robber (tổng lớn nhất khi không lấy hai phần tử kề nhau), Kadane (mảng con có tổng lớn nhất), coin change (số xu ít nhất). Bốn bài này hay xuất hiện làm bài con bên trong các bài Leetcode medium.

Bài 03: DP 2D, LCS và Edit Distance mở rộng state lên 2 chiều. LCS và Edit Distance cùng dùng bảng dp[i][j] nhưng transition khác nhau — một bài đếm chung, một bài đếm thao tác. Hai bài toán này là nền tảng của git diff và spell checker.

Bài 04: Knapsack là bài toán DP kinh điển nhất về tối ưu hoá có ràng buộc: chọn các món đồ sao cho tổng giá trị lớn nhất mà không vượt giới hạn trọng lượng. Knapsack 0/1 không giải được bằng greedy, và đó cũng là lý do module xếp knapsack trước greedy: để có sẵn một counter-example (ví dụ cho thấy greedy sai).

Bài 05: Greedy đến sau knapsack có chủ đích: bạn vừa thấy bài toán DP cần xét mọi lựa chọn, giờ học khi nào một lựa chọn tham lam là đủ. Interval scheduling và Huffman coding là hai ví dụ greedy đúng, nhưng chứng minh theo hai kiểu: interval scheduling bằng greedy stays ahead (greedy luôn không tệ hơn nghiệm tối ưu ở từng bước), Huffman bằng exchange argument (hoán đổi từng phần tử của nghiệm tối ưu sang lựa chọn của greedy mà không làm nghiệm tệ đi).

Bài 06: Backtracking khép lại tam giác: khi greedy sai và không gian nghiệm quá lớn cho DP, backtracking liệt kê có hệ thống mọi nghiệm và dùng pruning để bỏ bớt nhánh. Permutations, subsets, N-queens đều cùng một khung: choose → explore → unchoose.

Bài 07: Mini-challenge áp dụng DP 2D vào edit distance bằng bài tập có hướng dẫn, làm cầu nối giữa học lý thuyết và tự cài đặt từ đầu.

Bài 08: Case study đọc cơ chế thật của hai công cụ hàng ngày: LCS trong git diff (Myers algorithm) và Huffman trong gzip. Bài này không dạy kỹ thuật mới, mà cho thấy bạn đã đủ kiến thức để hiểu các công cụ production.

Bài 09: Tổng kết gom cheat sheet, glossary và self-assessment.

Bản đồ khái niệm

Thứ tự ba câu hỏi không tuỳ tiện. Hỏi greedy trước vì nó rẻ nhất, và vì greedy không đòi hỏi bài con lặp lại: interval scheduling ở bài 05 không có bài con nào lặp mà vẫn là bài greedy kinh điển. Chỉ khi không chứng minh nổi greedy-choice property mới cần tới DP.

Cách học module này hiệu quả

Implement từ đầu, không copy-paste. DP đặc biệt cần viết tay ít nhất một lần để cảm nhận tại sao thứ tự vòng lặp quan trọng. Memoization dễ viết hơn tabulation — bắt đầu từ đó, sau đó chuyển sang tabulation để hiểu thứ tự tính.

Vẽ bảng DP thủ công cho bài 2D. Trước khi code LCS hay Edit Distance, lấy giấy kẻ ô và điền dp[i][j] bằng tay cho ví dụ nhỏ (4-5 ký tự). Bước này giúp bạn thấy transition rõ hơn bất kỳ lời giải thích nào, và đúng tinh thần làm tay trước khi làm máy ở khoá tư duy lập trình.

Với greedy, luôn hỏi "ví dụ nào làm nó sai?". Trước khi tin một lời giải greedy, thử tìm một bộ input làm nó sai. Sau 10 phút vẫn không tìm ra ví dụ nào làm nó sai thì bắt đầu nghĩ đến exchange argument.

Với backtracking, vẽ cây quyết định nhỏ. N-queens với n=4 hay permutations của 3 phần tử đủ để thấy cấu trúc cây và hiểu pruning cắt bỏ nhánh nào.

Nối với bài toán thực tế ở bài 08. Đọc case study sau khi học xong bài 03 (LCS) và bài 05 (Greedy/Huffman) để thấy ngay mối liên hệ với git và gzip.

Time budget

Bài tiếp theo: Dynamic Programming — framework