Quyết định dưới constraint: tổng kết và cheat sheet

TL;DR: Module này cho bạn một tam giác quyết định: dùng DP khi bài con lặp lại và đáp án bài lớn ghép được từ đáp án tối ưu của các bài con, dùng Greedy khi chứng minh được greedy-choice property, dùng Backtracking khi cần liệt kê nghiệm và có thể cắt tỉa. Trang này là cheat sheet để bookmark: bảng khi nào dùng gì, 13 thuật ngữ cốt lõi, 5 bẫy hay gặp nhất và 4 câu tự kiểm tra. Nếu bạn giải thích được vì sao coin change dùng DP mà interval scheduling dùng greedy, và thiết kế được backtracking cho N-queens với pruning, bạn đã sẵn sàng cho module Pattern matching & String.

Đã đi qua những gì

Bạn bắt đầu từ bài 00 — Tổng quan module: ba kỹ thuật liên quan 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 bao quát nhất nhưng chạy theo hàm mũ.

Bốn bài DP (01 đến 04) dựng khuôn state, transition, base case rồi áp lên mảng 1D, bảng 2D (LCS, edit distance) và knapsack, nơi greedy bắt đầu lộ chỗ sai. Bài 05 cho greedy một nền chứng minh, bài 06 thêm backtracking cho những chỗ cả hai không với tới. Bài 07 bắt bạn tự cài đặt edit distance có trọng số, và bài 08 đọc lại diff, merge của git và nén gzip bằng đúng những công cụ đó.