Module 1 — Quyết định dưới constraint: tổng quan

TL;DR: Module 1 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ả subproblem để không tính lại, Greedy chọn cục bộ tốt nhất và chứng minh nó đúng toàn cục, Backtracking thử hệ thống toàn bộ không gian nghiệm với cắt tỉa sớm. Đây là module đầu của tier 3 — thuật toán ứng dụng — nơi ba công cụ này xuất hiện trong production hàng ngày dưới dạng git diff, gzip, và engine tìm kiếm.

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 dòng chung dài nhất giữa hai phiên bản file. Mỗi lần file của bạn được nén thành .gz, Huffman coding — thuật toán greedy — xây một 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 trình biên dịch giải quyết bài toán register allocation, hay AI của game tìm đường đi trong bản đồ, backtracking và biến thể của nó đang chạy bên dưới.

Khoá Thuat toan co the đã cho bạn đồ hộp công cụ: 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à nơi Leetcode medium/hard sống, và là nơi nhiều bài toán engineering thực tế sống.

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

• DP là công cụ mạnh nhất — đúng với mọi bài có overlapping subproblems và optimal substructure, nhưng tốn O(n²) hoặc O(n×W) không gian/thời gian.
• Greedy là công cụ nhanh nhất — O(n log n) thường gặp — nhưng chỉ đúng khi chứng minh được greedy choice property. Không chứng minh được → đừng dùng.
• Backtracking là công cụ toàn diện nhất — đúng với mọi bài tổ hợp — nhưng O(n!) hoặc O(2ⁿ) worst case. Pruning là chìa khoá giảm thời gian thực tế.

Biết cả ba, bạn có tam giác quyết định: thử greedy trước (nhanh nhất), chuyển sang DP nếu greedy không chứng minh được, dùng backtracking khi không gian nghiệm cần enumerate với constraint phức tạp.

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 — khi nào dùng cái nào, trade-off về stack depth và space.
• Implement DP 1D/2D và knapsack — thiết kế state, transition, base case cho bài toán mới bằng quy trình 5 bước từ bài 01.
• Justify tính đúng của greedy bằng greedy-choice property và exchange argument, và nhận ra khi nào greedy SAI — coin change với mệnh giá lạ, 0/1 knapsack.
• 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 — và phân tích complexity với/không có pruning.

Lộ trình module

flowchart LR
    OV["00\nTổng quan"] --> DP1["01\nDP Framework\n5 bước"]
    DP1 --> DP2["02\nDP 1D\nPatterns"]
    DP2 --> DP3["03\nDP 2D\nLCS & Edit"]
    DP3 --> KN["04\nKnapsack\n0/1 & variants"]
    KN --> GR["05\nGreedy\nExchange arg"]
    GR --> BT["06\nBacktracking\nPruning"]
    BT --> MC["07\nMini-challenge\nEdit distance"]
    MC --> CS["08\nCase study\nDiff & gzip"]
    CS --> REC["09\nTổng kết"]

Thứ tự bài — vì sao thiết kế như vậy

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, tối ưu space. Fibonacci là bài toán nhỏ nhất minh hoạ đủ tất cả năm bước — từ O(2ⁿ) naive xuống O(n) memo xuống O(1) space.

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 (max không kề nhau), Kadane (max subarray), coin change (đếm xu ít nhất). Bốn bài này xuất hiện như "sub-bài" trong hầu hết bài medium Leetcode.

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 items sao cho giá trị tối đa trong giới hạn trọng lượng. Knapsack 0/1 không giải được bằng greedy — đây cũng là lý do module xếp knapsack trước greedy, để tạo counter-example cụ thể.

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 — cả hai đều có chứng minh bằng exchange argument đầy đủ.

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 enumerate hệ thống với pruning. 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 — cầu nối giữa học lý thuyết và tự implement 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 — nó cho thấy bạn đã biết tất cả để hiểu production tools.

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

Bản đồ khái niệm

graph TD
    PROB["Bài toán tối ưu\nhoặc tổ hợp"] --> Q1{"Overlapping\nsubproblems?"}
    Q1 -- "Có" --> Q2{"Greedy choice\nproperty?"}
    Q2 -- "Có + chứng minh được" --> GREEDY["Greedy\nO(n log n)"]
    Q2 -- "Không chứng minh được" --> DP["Dynamic Programming\nO(n²) hoặc O(n·W)"]
    Q1 -- "Không" --> Q3{"Cần enumerate\ntất cả nghiệm?"}
    Q3 -- "Có" --> BT["Backtracking + Pruning\nO(n!) worst case"]
    Q3 -- "Không" --> DC["Divide & Conquer\nhoặc đơn giản hơn"]

    GREEDY --> EX1["Interval scheduling\nHuffman coding"]
    DP --> EX2["Knapsack, LCS\nEdit distance, Coin change"]
    BT --> EX3["Permutations, Subsets\nN-Queens, Sudoku"]

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] tay cho ví dụ nhỏ (4-5 ký tự). Bước này giúp nhận ra transition rõ hơn bất kỳ giải thích nào.

Với greedy, luôn hỏi "counter-example là gì?". Trước khi tin một greedy solution, thử tìm một bộ input làm nó sai. Không tìm được counter-example sau 10 phút → 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.

Liên hệ 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 connection với git và gzip.

Time budget

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