Quyết định dưới constraint — DP, Greedy, Backtracking

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

DP, Greedy, Backtracking — ba công cụ quyết định tối ưu backend dùng hàng ngày: git diff chạy LCS, gzip chạy Huffman, scheduler dùng greedy.

Dynamic Programming — framework 5 bước để giải quyết bài toán tối ưu

DP loại bỏ tính lại subproblem trùng bằng memoization/tabulation, cắt từ O(2^n) xuống O(n). Nắm 2 điều kiện DP, state + transition + base case qua quy trình 5 bước.

DP 1D — Climbing Stairs, House Robber, Kadane, Coin Change

Bốn bài DP 1D kinh điển dạy pattern cốt lõi: dp[i] phụ thuộc vài dp trước. Trace bảng dp từng bước, phân tích transition, và tối ưu space từ O(n) xuống O(1).

DP hai chiều — LCS và Edit Distance: bảng dp[i][j] và truy vết

LCS và Edit Distance dùng bảng 2D dp[i][j], state là hai prefix. Nắm transition, điền bảng, truy vết reconstruct — ứng dụng trong diff tool và spell-checker.

Bài toán cái túi — 0/1 Knapsack, Unbounded và tối ưu không gian

Knapsack chọn items tối đa value trong giới hạn W. Nắm 0/1 knapsack (dp[i][w] 2D → 1D), unbounded knapsack, vì sao greedy sai với counter-example, và liên hệ coin change.

Greedy — Tham lam có chứng minh: Interval Scheduling và Huffman

Greedy chọn tốt nhất mỗi bước không nhìn lại. Nắm greedy choice property, exchange argument, interval scheduling theo finish time, Huffman coding, và khi nào greedy SAI.

Backtracking và cắt tỉa — Permutations, N-Queens, pruning

Backtracking tìm kiếm có hệ thống: choose → explore → unchoose. Nắm khung tổng quát, permutations, subsets, N-queens, pruning cắt tỉa sớm, và phân tích độ phức tạp mũ.

Mini-challenge — Edit Distance: khoảng cách sửa giữa 2 chuỗi

Implement editDistance(s, t) trả số phép chèn/xoá/thay tối thiểu — DP 2D cổ điển nằm sau autocorrect, spell-check, diff tool, và bioinformatics sequence alignment.

Case Study: LCS trong git diff & Huffman trong gzip

git diff dùng LCS/Myers để tìm minimal diff, gzip/DEFLATE dùng Huffman coding để nén theo tần suất ký tự — hai công cụ hàng ngày ẩn chứa DP cổ điển.

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.