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

TL;DR: Dynamic Programming (DP) là kỹ thuật tối ưu hoá bằng cách chia bài toán lớn thành subproblem nhỏ hơn, lưu kết quả để không tính lại. Hai điều kiện cần: (1) overlapping subproblems — cùng subproblem xuất hiện nhiều lần; (2) optimal substructure — solution tối ưu của bài lớn được xây từ solution tối ưu của subproblem. Có hai cách implement: memoization (top-down, đệ quy + cache) và tabulation (bottom-up, điền bảng). Quy trình thiết kế 5 bước: xác định state → viết transition → base case → thứ tự tính → tối ưu không gian.

Một sinh viên code Fibonacci naive và chờ 30 giây để tính fib(45). Thêm 4 dòng cache, thời gian giảm xuống dưới 1 millisecond. Không phải thuật toán khác — vẫn cùng công thức, chỉ không tính lại subproblem đã có đáp án.

Đây là cốt lõi của Dynamic Programming: nhận ra rằng bài toán đang tính đi tính lại cùng một thứ, và ngăn chặn điều đó bằng cách lưu lại kết quả. DP không phải một công thức ma thuật — nó là một tư duy hệ thống để chuyển đệ quy mũ thành đa thức.

Module này dạy DP framework: hai điều kiện, hai cách implement, và quy trình 5 bước để thiết kế solution từ đầu.

1. Analogy — Sổ tay tính toán

Hãy tưởng tượng bạn đang giải một bài toán có nhiều câu hỏi con. Cách naive: mỗi lần gặp câu hỏi con, bạn ngồi tính lại từ đầu — dù đã tính câu đó hàng chục lần trước. Cách thông minh: mỗi khi tính xong câu hỏi nào, ghi đáp án vào sổ tay. Lần sau gặp lại, tra sổ thay vì tính lại.

DP là chiếc sổ tay đó — chỉ tính mỗi subproblem đúng một lần.

2. Hai điều kiện của DP

2.1 Overlapping subproblems

Bài toán có overlapping subproblems khi cùng một subproblem nhỏ hơn xuất hiện nhiều lần trong quá trình giải bài toán lớn.

Fibonacci là ví dụ kinh điển. Để tính fib(5), cần fib(4) và fib(3). Để tính fib(4), lại cần fib(3) và fib(2). fib(3) xuất hiện ít nhất 2 lần — và với n lớn hơn, số lần trùng lặp tăng theo cấp số nhân.

graph TD
    F5["fib(5)"]
    F4a["fib(4)"]
    F3a["fib(3)"]
    F3b["fib(3) ← trùng!"]
    F2a["fib(2)"]
    F2b["fib(2) ← trùng!"]
    F2c["fib(2) ← trùng!"]
    F1a["fib(1)"]
    F1b["fib(1)"]
    F1c["fib(1)"]
    F0a["fib(0)"]
    F0b["fib(0)"]

    F5 --> F4a
    F5 --> F3b
    F4a --> F3a
    F4a --> F2a
    F3a --> F2b
    F3a --> F1a
    F3b --> F2c
    F3b --> F1b
    F2a --> F1c
    F2a --> F0a
    F2b --> F0b

Cây đệ quy naive có fib(3) xuất hiện 2 lần, fib(2) xuất hiện 3 lần. Với fib(50), có hàng tỷ lần tính trùng — đó là lý do complexity là O(2^n).

Ngược lại: merge sort chia mảng thành hai nửa không giao nhau — subproblem không trùng lặp, nên không dùng DP mà dùng divide and conquer.

2.2 Optimal substructure

Bài toán có optimal substructure khi solution tối ưu của bài toán lớn có thể được xây dựng từ solution tối ưu của các subproblem nhỏ hơn.

Ví dụ: shortest path từ A đến C qua B. Nếu path A → B → C là shortest từ A đến C, thì A → B phải là shortest từ A đến B, và B → C phải là shortest từ B đến C. Nếu có path ngắn hơn từ A đến B, ta có thể thay vào để cải thiện path A đến C — mâu thuẫn với giả thiết.

Bài toán không có optimal substructure: longest simple path (đường đi dài nhất không lặp đỉnh). Path dài nhất từ A đến C không nhất thiết đi qua path dài nhất từ A đến B — vì thêm đoạn B→C có thể làm path từ A đến B phải ngắn hơn để tránh lặp đỉnh.

3. Hai cách implement DP

3.1 Memoization — top-down

Memoization (hay top-down DP) giữ nguyên cấu trúc đệ quy nhưng thêm một bảng cache. Trước khi tính, kiểm tra cache; nếu đã có, trả về ngay.

-- Top-down: đệ quy + cache
memo <- mảng rỗng (chưa tính)

fib_memo(n):
    if n <= 1: return n
    if memo[n] != UNSET: return memo[n]   -- đã tính, tra cache
    memo[n] <- fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

Time: O(n) Space: O(n) cho memo + O(n) call stack

Mỗi giá trị fib(k) chỉ được tính đúng một lần. Lần đầu: đệ quy xuống, tính rồi lưu vào memo[k]. Mọi lần sau: tra cache, trả về O(1).

3.2 Tabulation — bottom-up

Tabulation (hay bottom-up DP) loại bỏ đệ quy hoàn toàn. Thay vào đó, điền bảng dp[] từ base case nhỏ nhất lên đến answer.

-- Bottom-up: điền bảng từ nhỏ đến lớn
fib_tab(n):
    dp[0] <- 0
    dp[1] <- 1
    for i <- 2 đến n:
        dp[i] <- dp[i-1] + dp[i-2]
    return dp[n]

Time: O(n) Space: O(n)

Không có đệ quy — không có stack overflow risk. Thứ tự vòng lặp i = 2, 3, ..., n đảm bảo khi tính dp[i], cả dp[i-1] và dp[i-2] đã sẵn sàng.

3.3 So sánh hai cách

4. Ví dụ đầy đủ — Fibonacci: từ O(2^n) xuống O(n)

4.1 Naive — O(2^n)

fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)

Time: O(2^n) Space: O(n) call stack

Với n = 50: khoảng 2^50 ≈ 10^15 lần gọi hàm. Không thực tế.

4.2 Sau khi thêm memo — O(n)

memo <- array[-1, -1, ..., -1] độ dài n+1   -- -1 = chưa tính

fib_memo(n):
    if n <= 1: return n
    if memo[n] != -1: return memo[n]
    memo[n] <- fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

Time: O(n) Space: O(n)

Cây đệ quy "phẳng" ra: mỗi node chỉ được tính một lần, tổng n lần gọi thực sự.

4.3 Tối ưu space xuống O(1)

dp[i] chỉ phụ thuộc dp[i-1] và dp[i-2] — không cần giữ toàn bộ mảng:

fib_opt(n):
    if n <= 1: return n
    prev2 <- 0    -- fib(0)
    prev1 <- 1    -- fib(1)
    for i <- 2 đến n:
        cur <- prev1 + prev2
        prev2 <- prev1
        prev1 <- cur
    return prev1

Time: O(n) Space: O(1)

5. Quy trình 5 bước thiết kế DP

Mọi bài DP đều có thể thiết kế theo 5 bước sau:

Bước 1 — Xác định state

State là "tham số" của subproblem — đủ thông tin để tính kết quả của subproblem đó mà không cần biết lịch sử đã đến state này như thế nào.

Câu hỏi: "Tôi cần biết gì để giải subproblem?"

• Fibonacci: state = n (index cần tính)
• Climbing stairs: state = i (đang ở bậc thứ i, cần lên bậc n)
• Knapsack 0/1: state = (i, w) — đang xét item i, còn w kg trọng lượng tối đa

Bước 2 — Viết transition (recurrence relation)

Transition là công thức tính dp[state] từ các state nhỏ hơn đã được giải.

Câu hỏi: "State này được tính từ state nào?"

-- Fibonacci:
dp[i] = dp[i-1] + dp[i-2]

-- Climbing stairs (leo 1 hoặc 2 bậc):
dp[i] = dp[i-1] + dp[i-2]

-- Coin change (tìm số xu ít nhất):
dp[i] = min(dp[i - coin] + 1) cho mọi coin trong danh sách xu

Bước 3 — Base case

Base case là các subproblem nhỏ nhất có thể trả lời trực tiếp mà không cần chia nhỏ hơn nữa.

-- Fibonacci:
dp[0] = 0,  dp[1] = 1

-- Climbing stairs:
dp[0] = 1   -- 1 cách đứng ở mặt đất (không bước)
dp[1] = 1   -- 1 cách lên bậc 1 (1 bước)

-- Coin change:
dp[0] = 0   -- cần 0 xu để đạt tổng 0

Bước 4 — Thứ tự tính (nếu dùng tabulation)

Đảm bảo khi tính dp[state], tất cả state nó phụ thuộc đã được tính trước.

• 1D DP (Fibonacci, climbing stairs): tính từ 0 đến n.
• 2D DP (LCS, edit distance): thường tính từ (0,0) đến (m,n) — hàng trước cột trước.

Bước 5 — Tối ưu không gian (tuỳ chọn)

Nếu transition chỉ phụ thuộc vào một vài state gần, có thể giảm space từ O(n) xuống O(1) hoặc từ O(mn) xuống O(n).

-- Chỉ cần 2 state gần nhất → dùng 2 biến thay mảng:
prev2, prev1  -- thay dp[0..n]

6. Pitfall — Thiếu base case hoặc sai thứ tự

Pitfall 1 — Quên base case

-- BUG: không có base case, infinite recursion
fib_bug(n):
    return fib_bug(n-1) + fib_bug(n-2)   -- không dừng khi n <= 1

-- CORRECT: base case dừng đệ quy
fib_correct(n):
    if n <= 1: return n                   -- base case
    return fib_correct(n-1) + fib_correct(n-2)

Pitfall 2 — Sai thứ tự tính trong tabulation

-- BUG (bottom-up coin change): tính dp[i] trước khi dp[i - coin] sẵn sàng
for coin in coins:
    for i <- 0 đến amount:               -- thứ tự sai cho unbounded knapsack
        ...

-- CORRECT: với unbounded coin change, tính theo amount tăng dần
for i <- 1 đến amount:
    for coin in coins:
        if i >= coin:
            dp[i] <- min(dp[i], dp[i - coin] + 1)

Pitfall 3 — State không đủ thông tin

-- BUG: state thiếu — không thể xác định kết quả chỉ từ position
-- Ví dụ robot đi trên grid có obstacle — state chỉ lưu (i, j) là đủ
-- NHƯNG: nếu có thêm ràng buộc "đã dùng bao nhiêu bước đặc biệt"
-- thì state phải là (i, j, k) — thiếu k sẽ cho kết quả sai

Khi gặp kết quả sai, câu hỏi đầu tiên: "State định nghĩa có đủ thông tin chưa?"

7. Liên hệ các bài khác

• Recursion và call stack: Memoization là đệ quy + cache — phải hiểu call stack trước để thấy tại sao top-down có stack overflow risk với n lớn.
• Amortized analysis: DP đạt O(n) nhờ mỗi subproblem tính đúng 1 lần — amortized cost O(1) mỗi subproblem. Cùng tư duy "trải đều chi phí".
• DP một chiều: Bài tiếp theo áp dụng framework 5 bước vào 4 pattern 1D: climbing stairs, house robber, Kadane, coin change.
• LCS và Edit Distance: Mở rộng lên state 2 chiều dp[i][j] — transition phức tạp hơn nhưng cùng framework.
• Knapsack: Bài toán DP kinh điển có state 2 chiều (item, capacity).

📚 Deep Dive

Tóm tắt

• DP giải bài toán tối ưu bằng cách chia thành subproblem, lưu kết quả để không tính lại.
• Hai điều kiện: overlapping subproblems (subproblem trùng lặp) + optimal substructure (giải tối ưu xây từ subproblem tối ưu).
• Memoization (top-down): đệ quy + cache — giữ logic đệ quy, lazy evaluation.
• Tabulation (bottom-up): vòng lặp + mảng — không stack overflow, dễ tối ưu space.
• Quy trình 5 bước: xác định state → viết transition → base case → thứ tự tính → tối ưu space.
• Fibonacci naive O(2^n) → với memo O(n) → tối ưu space O(1).
• Pitfall hay gặp: quên base case, sai thứ tự tabulation, state không đủ thông tin.

Tự kiểm tra

Bài tiếp theo: DP một chiều — climbing stairs, house robber, Kadane, coin change