Quy hoạch động & tham lam: nghệ thuật không tính lại cái đã tính

Có một loại bài toán mà cách giải "thẳng thớm" nhất — thử mọi khả năng — lại chậm đến mức vô dụng: số bước tăng theo hàm mũ, và với đầu vào chỉ vài chục phần tử đã mất hàng thế kỷ. Nhưng khi nhìn kỹ, ta phát hiện phần lớn công sức bị lãng phí vào việc giải đi giải lại cùng một bài toán con. Quy hoạch động (dynamic programming, DP) là kỹ thuật xoá bỏ sự lãng phí đó: giải mỗi bài toán con đúng một lần, ghi nhớ kết quả, rồi tái sử dụng. Kết quả là độ phức tạp tụt từ mũ xuống đa thức — thường là bước ngoặt giữa "không thể" và "chạy trong tích tắc".

Bài này đi cùng cặp với Độ phức tạp thuật toán (để đo được cái lợi của DP), Sắp xếp & tìm kiếm và Chuỗi & băm (nơi edit distance được dùng nhiều nhất). Toàn bộ mã ở đây thuộc danh mục Python; sandbox của khoá là PostgreSQL nên Python không chạy trực tiếp tại đây — mọi khối mã là (minh hoạ) để hiểu ý đồ rồi mang về dự án thật.

1. Khi nào dùng DP: hai điều kiện phải có

DP không phải cây búa vạn năng. Nó chỉ áp dụng được khi bài toán thoả cả hai tính chất sau:

• Bài toán con gối nhau (overlapping subproblems): khi giải bằng đệ quy, cùng một bài toán con xuất hiện lặp lại nhiều lần. Đây là điều khiến việc ghi nhớ có ích — nếu mỗi bài toán con chỉ gặp một lần thì cache không cứu được gì (đó là địa hạt của chia để trị như merge sort).
• Cấu trúc con tối ưu (optimal substructure): lời giải tối ưu của bài toán lớn có thể ghép từ lời giải tối ưu của các bài toán con. Nếu tối ưu con không kéo theo tối ưu tổng, DP kiểu thẳng sẽ cho kết quả sai.

Cách nhận diện "mùi DP" trong thực tế: bạn thấy mình đang thử mọi cách chọn (chọn hay không chọn phần tử, cắt chuỗi ở đâu, đi hướng nào), lời giải phân rã tự nhiên theo một hoặc hai chỉ số (vị trí, dung lượng còn lại, độ dài đã xử lý), và các nhánh đệ quy đụng lại cùng trạng thái. Khi đó không gian trạng thái hữu hạn, và DP biến bài toán mũ thành duyệt bảng đa thức.

2. Fibonacci: minh hoạ sạch nhất của "gối nhau"

Định nghĩa fib(n) = fib(n-1) + fib(n-2). Cài đệ quy ngây thơ, cây gọi hàm phình ra theo cấp số nhân vì fib(n-2) được tính lại ở nhiều nhánh:

Nhìn các ô cùng màu: fib(3) được tính hai lần, fib(2) ba lần. Càng lên cao càng nổ — độ phức tạp là O(φⁿ) (mũ). Đây chính là overlapping subproblems ở dạng thuần khiết nhất. Ghi nhớ (memo) biến cây thành đồ thị: mỗi trạng thái chỉ tính một lần.

2.1. Memoization (top-down): đệ quy + cache

Giữ nguyên tư duy đệ quy tự nhiên, chỉ thêm một tầng cache. Trong Python, functools.lru_cache làm việc này gần như miễn phí:

# (minh hoạ)
from functools import lru_cache

@lru_cache(maxsize=None)          # cache tự động theo tham số
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# fib(100) trả về tức thì thay vì treo máy

lru_cache băm tham số làm khoá, lưu kết quả, và lần sau gọi cùng n thì trả thẳng từ dict. Độ phức tạp rơi từ O(φⁿ) xuống O(n) thời gian, O(n) bộ nhớ. Lưu ý: tham số phải hashable (immutable) — không truyền list hay dict; nếu cần thì đổi sang tuple.

2.2. Tabulation (bottom-up): điền bảng từ nhỏ tới lớn

Cách còn lại là bỏ đệ quy, giải các bài con nhỏ nhất trước rồi bồi dần lên:

# (minh hoạ)
def fib_tab(n: int) -> int:
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Vì mỗi giá trị chỉ phụ thuộc hai giá trị liền trước, ta có thể tối ưu bộ nhớ từ O(n) xuống O(1) bằng cách chỉ giữ hai biến cuộn (rolling variables):

# (minh hoạ)
def fib_o1(n: int) -> int:
    prev, cur = 0, 1
    for _ in range(n):
        prev, cur = cur, prev + cur
    return prev

2.3. Memoization vs tabulation: đánh đổi

Nguyên tắc thực dụng: prototype bằng memoization (lru_cache) cho nhanh và ít sai; nếu cần siết bộ nhớ hoặc tránh giới hạn đệ quy thì viết lại thành tabulation rồi giảm chiều bảng.

3. Edit distance (Levenshtein): trái tim của fuzzy matching

Đây là ví dụ DP có giá trị thực tế lớn nhất trong ngành ngân hàng/dữ liệu. Khoảng cách chỉnh sửa (edit distance) giữa hai chuỗi là số phép biến đổi tối thiểu — chèn, xoá, thay một ký tự — để biến chuỗi này thành chuỗi kia. Levenshtein tính đúng ba phép đó.

Công thức truy hồi: gọi d[i][j] là edit distance giữa i ký tự đầu của a và j ký tự đầu của b.

• Nếu a[i-1] == b[j-1]: d[i][j] = d[i-1][j-1] (ký tự trùng, không tốn phép nào).
• Ngược lại: d[i][j] = 1 + min(d[i-1][j], d[i][j-1], d[i-1][j-1]) — tương ứng xoá, chèn, thay.

Bài toán này gối nhau (ô d[i][j] phụ thuộc các ô đã tính) và có cấu trúc con tối ưu, nên DP dùng đúng. Bảng bottom-up:

# (minh hoạ)
def edit_distance(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i           # biến a[:i] thành rỗng: i lần xoá
    for j in range(n + 1):
        dp[0][j] = j           # từ rỗng thành b[:j]: j lần chèn
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],       # xoá
                    dp[i][j - 1],       # chèn
                    dp[i - 1][j - 1],   # thay
                )
    return dp[m][n]

# edit_distance("NGUYEN VAN A", "NGUYEN VAN Á") == 1

Độ phức tạp: O(m·n) thời gian, O(m·n) bộ nhớ. Vì mỗi hàng chỉ dùng hàng ngay trên, có thể giảm bộ nhớ xuống O(min(m, n)) bằng hai hàng cuộn. Lưu ý lý thuyết: Levenshtein không thể tính nhanh hơn dưới bậc hai (subquadratic) trừ khi giả thuyết SETH sai — nên O(m·n) là ngưỡng thực tế, và với danh sách dài ta phải chặn trước bằng blocking/indexing thay vì so mọi cặp.

3.1. Longest common subsequence (LCS): nền của diff & đối soát

Cùng họ với edit distance, LCS tìm dãy con chung dài nhất (không cần liền kề) giữa hai chuỗi. Đây là nền của công cụ diff và của đối soát dữ liệu: so hai phiên bản một bảng/tệp, tìm dòng khớp để suy ra dòng nào bị thêm/xoá/sửa.

# (minh hoạ)
def lcs_len(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

3.2. Knapsack (cái túi): phân bổ tài nguyên có ràng buộc

Cho các món có giá trị và trọng lượng, chọn tập món để tối đa hoá tổng giá trị mà không vượt sức chứa W. Đây là khung mẫu cho phân bổ hạn mức/ngân sách/tài nguyên có ràng buộc — ví dụ chọn tập dự án/khoản đầu tư để tối đa lợi ích dưới trần vốn.

# (minh hoạ) 0/1 knapsack
def knapsack(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w_i, v_i = weights[i - 1], values[i - 1]
        for cap in range(W + 1):
            dp[i][cap] = dp[i - 1][cap]                 # không lấy món i
            if w_i <= cap:                               # hoặc lấy nếu vừa
                dp[i][cap] = max(dp[i][cap],
                                 dp[i - 1][cap - w_i] + v_i)
    return dp[n][W]

Trạng thái là (số món đã xét, dung lượng còn lại), nên độ phức tạp là O(n·W). Lưu ý quan trọng: đây là giả đa thức (pseudo-polynomial) — phụ thuộc vào giá trị W chứ không phải số bit của nó. Nếu W khổng lồ, bảng nổ; đó là ranh giới nơi DP hết hiệu quả.

4. Greedy (tham lam): chọn tối ưu cục bộ từng bước

Greedy đơn giản đến bất ngờ: ở mỗi bước, chọn phương án trông tốt nhất ngay lúc đó và không bao giờ nhìn lại. Không có bảng, không quay lui. Khi đúng, greedy nhanh hơn DP nhiều (thường O(n log n) do phải sắp xếp trước).

Khi nào greedy đúng? Khi bài toán có cấu trúc con tối ưu và thoả tính chất lựa chọn tham lam (greedy-choice property): một lựa chọn tối ưu cục bộ luôn nằm trong một lời giải tối ưu toàn cục. Về mặt hình thức, lớp bài toán mà greedy chắc chắn đúng gắn với cấu trúc matroid (Edmonds): greedy giải tối ưu các bài toán tối ưu tuyến tính trên matroid. Ngoài lớp đó, greedy có thể sai thảm hại trên những bài mà DP giải dễ dàng — sức mạnh của hai kỹ thuật là không so sánh được (incomparable).

4.1. Coin change: nơi greedy đúng rồi bỗng sai

Bài đổi tiền: dùng ít đồng nhất để đủ số tiền amount. Với bộ mệnh giá "chuẩn" (canonical) như VND thực tế hay USD, tham lam — cứ lấy đồng lớn nhất còn dùng được — cho kết quả tối ưu:

# (minh hoạ) greedy — đúng với mệnh giá canonical
def coin_greedy(coins: list[int], amount: int) -> int:
    coins = sorted(coins, reverse=True)
    count = 0
    for c in coins:
        take = amount // c
        count += take
        amount -= take * c
    return count if amount == 0 else -1   # có thể không đổi được

Nhưng đổi bộ mệnh giá "lạ" thì greedy sai. Kinh điển: coins = [1, 3, 4], amount = 6. Greedy lấy 4 rồi 1 + 1 → 3 đồng; trong khi tối ưu là 3 + 3 → 2 đồng. Lời giải đúng cho mọi bộ mệnh giá là DP:

# (minh hoạ) DP — đúng với MỌI mệnh giá
def coin_dp(coins: list[int], amount: int) -> int:
    INF = amount + 1
    dp = [0] + [INF] * amount          # dp[x] = số đồng ít nhất đổi ra x
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

# coin_dp([1, 3, 4], 6) == 2   (đúng), còn coin_greedy trả 3 (sai)

Bài học: thấy greedy đừng vội tin — hãy tìm phản ví dụ, hoặc chứng minh greedy-choice property. Nếu không chắc, DP là chốt an toàn.

4.2. Interval scheduling: nơi greedy chắc chắn đúng

Chọn nhiều nhất các khoảng thời gian không chồng lấn (ví dụ đặt lịch phòng họp, xếp job không đè nhau). Chiến lược tối ưu đã chứng minh được: sắp theo thời điểm kết thúc, luôn chọn khoảng kết thúc sớm nhất còn hợp lệ.

# (minh hoạ)
def max_non_overlap(intervals: list[tuple[int, int]]) -> int:
    intervals.sort(key=lambda iv: iv[1])   # sắp theo thời điểm kết thúc
    count, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

5. DP vs Greedy vs Brute-force: chọn cái nào

Cách nhận biết nhanh:

• Bài yêu cầu tối ưu (min/max) + lời giải phân rã theo vài chỉ số + các nhánh đụng lại cùng trạng thái → DP.
• Có chứng minh (hoặc trực giác vững) rằng lựa chọn cục bộ tốt nhất luôn an toàn → thử greedy, nhưng kiểm phản ví dụ.
• Đầu vào bé và cần lời giải chắc đúng để đối chiếu → brute-force làm "oracle" để test DP/greedy.

6. Use case thực tế: edit distance cho fuzzy matching AML

Đây là điểm gặp giữa thuật toán và tuân thủ. Trong sàng lọc cấm vận (AML), ta phải so tên khách hàng/giao dịch với danh sách trừng phạt (OFAC/UN/EU). Vấn đề: tên không bao giờ khớp chính xác — sai chính tả, phiên âm khác nhau, thiếu dấu, đảo họ-tên, bí danh. Khớp bằng dấu = sẽ bỏ lọt kẻ xấu chỉ vì lệch một ký tự.

Edit distance là công cụ đo "gần khớp" đó. Ta chuẩn hoá tên (viết hoa, bỏ dấu, gộp khoảng trắng), tính Levenshtein, rồi quy ra tỷ lệ tương đồng để đặt ngưỡng:

# (minh hoạ) fuzzy name matching cho sàng lọc AML
def similarity(a: str, b: str) -> float:
    dist = edit_distance(a.upper(), b.upper())
    longest = max(len(a), len(b)) or 1
    return 1.0 - dist / longest      # 1.0 = trùng khít, 0.0 = khác hẳn

def screen(name: str, watchlist: list[str], threshold: float = 0.85):
    return [w for w in watchlist if similarity(name, w) >= threshold]

# "NGUYEN VAN A" vs "NGUYEN VAN Á" → similarity ~ 0.92 → BÁO HIT

Ngưỡng là đánh đổi kinh điển: đặt cao thì bỏ lọt (false negative — rủi ro tuân thủ nghiêm trọng), đặt thấp thì ngập báo giả (false positive — đội chi phí điều tra). Vì edit distance là O(m·n) mỗi cặp, quét cả triệu tên là bất khả thi nếu so mọi cặp — nên thực tế phải chặn trước bằng blocking/indexing (chia nhóm theo phoneme, tiền tố, băm) rồi mới dùng edit distance tinh chỉnh trong nhóm nhỏ. Kỹ thuật băm/chuẩn hoá chuỗi này nối thẳng sang Chuỗi & băm. Cùng cơ chế còn phục vụ entity resolution — gộp các bản ghi cùng một khách hàng dù ghi tên/địa chỉ khác nhau.

Ngoài AML, các khung DP đã học lặp lại khắp nơi: knapsack cho phân bổ hạn mức/ngân sách dưới ràng buộc; LCS/diff cho đối soát hai phiên bản dữ liệu và tìm sai lệch trong reconciliation.

7. Giới hạn: khi state space nổ

DP đổi thời gian lấy bộ nhớ, và cái giá là kích thước không gian trạng thái. Nếu trạng thái cần nhiều chỉ số (nhiều chiều), bảng phình theo tích các chiều và có thể vượt RAM trước khi kịp chạy. Knapsack là ví dụ giả đa thức: O(n·W) trông "đa thức" nhưng thực chất mũ theo số bit của W. Khi state space nổ, lối ra là: giảm chiều bảng (rolling array), cắt tỉa trạng thái không đạt được, xấp xỉ (approximation), hoặc đổi hẳn sang heuristic/greedy chấp nhận lời giải gần tối ưu.

8. Ghi nhớ

• DP chỉ dùng được khi có cả hai: bài toán con gối nhau + cấu trúc con tối ưu. Thiếu gối nhau → chia để trị; thiếu cấu trúc tối ưu → DP thẳng cho sai.
• "Mùi DP": bài tối ưu (min/max), lời giải phân rã theo vài chỉ số, các nhánh đệ quy đụng lại cùng trạng thái.
• Prototype bằng memoization (functools.lru_cache, tham số phải hashable); cần siết bộ nhớ hoặc tránh tràn stack thì chuyển sang tabulation rồi giảm chiều bảng.
• Edit distance O(m·n) là nền của fuzzy name matching AML và entity resolution; đặt ngưỡng tương đồng để cân giữa bỏ lọt và báo giả; quét lớn phải blocking trước rồi mới so tinh.
• Greedy nhanh nhưng chỉ đúng có điều kiện (greedy-choice property / matroid). Coin change: greedy đúng với mệnh giá canonical, sai với mệnh giá lạ → DP mới tổng quát đúng. Thấy greedy phải tìm phản ví dụ.
• Cảnh giác state space nổ: knapsack là giả đa thức; khi bảng vượt RAM, giảm chiều / cắt tỉa / xấp xỉ / đổi sang heuristic.

Đọc tiếp: Độ phức tạp thuật toán để định lượng cái lợi của DP, Sắp xếp & tìm kiếm, Chuỗi & băm cho tối ưu fuzzy matching, và Sàng lọc cấm vận AML cho bức tranh nghiệp vụ đầy đủ.