Algorithms & Applications
Trang chủ / Module 8
🧩 Module 8 / 14 · 1-2 tuần

Quy hoạch động (Dynamic Programming)

Tư duy DP: nhận diện overlapping subproblems, Memoization (top-down) vs Tabulation (bottom-up), và luyện tập qua các bài toán kinh điển.

DPMemoization
📌 Vì sao module này quan trọng

Dynamic Programming là kỹ thuật bị coi là "khó nhất" trong thuật toán vì nó đòi hỏi nhận diện được cấu trúc ẩn của bài toán, không có công thức máy móc. Nhưng một khi nắm được khung tư duy đúng, DP giải quyết được lớp bài toán tối ưu hoá rất rộng mà Greedy không xử lý được đúng, và là chủ đề thường gặp nhất trong phỏng vấn thuật toán cấp cao.

🎯 Mục tiêu học tập

  • Nhận diện dấu hiệu 1 bài toán phù hợp với DP: Overlapping Subproblems và Optimal Substructure
  • Phân biệt và áp dụng Memoization (top-down) và Tabulation (bottom-up)
  • Giải các bài toán DP kinh điển: Fibonacci tối ưu, Knapsack, Longest Common Subsequence
  • Xây dựng được DP transition/recurrence relation cho 1 bài toán mới

Nhận diện bài toán DP

2 dấu hiệu cần có để áp dụng DP:

  • Overlapping Subproblems: giải pháp đệ quy "ngây thơ" tính đi tính lại cùng 1 bài toán con nhiều lần — ví dụ Fibonacci đệ quy thường tính fib(5) nhiều lần khi tính fib(10). DP lưu lại (cache) kết quả đã tính để không tính lại.
  • Optimal Substructure: lời giải tối ưu của bài toán lớn có thể xây dựng từ lời giải tối ưu của các bài toán con nhỏ hơn (giống Optimal Substructure của Greedy — Module 7, nhưng DP không cần Greedy Choice Property, phù hợp cho các bài toán phức tạp hơn mà Greedy thất bại).
# Fibonacci đệ quy "ngây thơ" — O(2^n), tính đi tính lại rất nhiều lần
def fib_cham(n):
    if n <= 1: return n
    return fib_cham(n - 1) + fib_cham(n - 2)

# fib_cham(5) gọi fib_cham(3) hai lần, fib_cham(2) ba lần... lãng phí rất lớn

Memoization (Top-down) vs Tabulation (Bottom-up)

# Memoization — vẫn đệ quy, nhưng lưu cache kết quả đã tính (top-down: từ bài toán lớn đi xuống)
def fib_memo(n, cache={}):
    if n in cache: return cache[n]
    if n <= 1: return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]
# O(n) time, O(n) space — giải quyết triệt để vấn đề tính lại

# Tabulation — không đệ quy, xây bảng kết quả từ dưới lên (bottom-up: từ bài toán nhỏ nhất đi lên)
def fib_tab(n):
    if n <= 1: 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]
# O(n) time, O(n) space (có thể tối ưu xuống O(1) space vì chỉ cần 2 giá trị gần nhất)
Memoization (Top-down)Tabulation (Bottom-up)
Cách viếtĐệ quy tự nhiên + cache — thường dễ viết hơn từ tư duy bài toán gốcVòng lặp xây bảng — cần xác định đúng thứ tự tính toán
Chỉ tính bài toán con cần thiết?Có — chỉ tính nhánh thực sự được gọi đếnKhông — thường tính toàn bộ bảng dù có thể không cần hết
Rủi ro Stack OverflowCó (đệ quy sâu) — liên hệ Module 2, 6Không (dùng vòng lặp)

Bài toán DP kinh điển: 0/1 Knapsack

Cho N vật phẩm (mỗi vật có trọng lượng và giá trị), và 1 túi có sức chứa W — chọn tập vật phẩm để tổng giá trị lớn nhất mà không vượt quá sức chứa (mỗi vật chỉ chọn 0 hoặc 1 lần). Công thức truy hồi (recurrence): với mỗi vật phẩm i, hoặc không lấy (giữ nguyên giá trị tối ưu của W với i-1 vật đầu), hoặc lấy (giá trị vật i + giá trị tối ưu của W-trọng_lượng[i] với i-1 vật đầu) — chọn phương án tốt hơn:

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

Bài toán Knapsack là mẫu hình cho rất nhiều bài toán "phân bổ tài nguyên có giới hạn" trong thực tế: phân bổ ngân sách marketing giữa các kênh, chọn tập tính năng phát triển trong 1 sprint có giới hạn thời gian đội ngũ, đóng gói tài nguyên vào container/VM có giới hạn CPU/RAM.

Longest Common Subsequence (LCS) — nền tảng của Diff Tools

Tìm chuỗi con chung dài nhất giữa 2 chuỗi (không cần liên tiếp, chỉ cần giữ đúng thứ tự) — đây chính là thuật toán nền tảng đứng sau git diff và các công cụ so sánh văn bản: tìm phần "giống nhau" giữa 2 phiên bản file để chỉ hiển thị phần thực sự thay đổi, thay vì coi toàn bộ file là mới.

🏋️ Bài tập thực hành

Giải 0/1 Knapsack và LCS

Triển khai đầy đủ 0/1 Knapsack bằng Tabulation. Triển khai Longest Common Subsequence cho 2 chuỗi bất kỳ, thử với 2 đoạn văn bản gần giống nhau và in ra chuỗi con chung tìm được. Với mỗi bài, viết rõ công thức truy hồi (recurrence relation) bằng lời trước khi viết code — đây là bước tư duy quan trọng nhất của DP, quan trọng hơn cả việc viết code.

📚 Tài nguyên học tập

✅ Tự đánh giá hoàn thành

  • Nhận diện được Overlapping Subproblems và Optimal Substructure trong 1 bài toán mới
  • Triển khai được cả Memoization và Tabulation cho cùng 1 bài toán
  • Giải đúng bài toán 0/1 Knapsack
  • Xây dựng được recurrence relation cho ít nhất 1 bài toán DP mới, chưa từng gặp