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 chia bài toán lớn thành các bài con nhỏ hơn, giải mỗi bài con một lần rồi lưu đáp án để khỏi tính lại. Dùng được khi có hai đặc điểm. Một: cùng một bài con bị hỏi đi hỏi lại nhiều lần (overlapping subproblems). Hai: đáp án tốt nhất của bài lớn ghép được từ đáp án tốt nhất của các bài con (optimal substructure). Có hai cách viết: memoization (top-down, đệ quy kèm 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, đặt base case, chọn thứ tự tính, nén bộ nhớ.

Một sinh viên code Fibonacci naive rồi ngồi chờ cả chục giây để tính fib(45). Thêm vài dòng cache, thời gian tụt xuống dưới 1 millisecond. Thuật toán không đổi, vẫn cùng công thức, chỉ là không tính lại những bài con đã có đáp án.

Đó là cốt lõi của Dynamic Programming: nhận ra bài toán tính đi tính lại cùng một thứ, rồi lưu kết quả lại. Bài này dạy khung làm DP: hai điều kiện, hai cách cài đặt, và quy trình 5 bước.

1. Hình dung: sổ tay tính toán

Cách naive: mỗi lần gặp câu hỏi con, bạn tính lại từ đầu. Cách thông minh: tính xong thì ghi đáp án vào sổ tay, lần sau tra sổ.

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

Nếu chưa quen việc điền bảng bằng tay, ôn lại bảng trace: bảng dp chính là một bảng trace do bạn tự thiết kế.

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

2.1 Overlapping subproblems

Nói bằng lời thường: bài lớn được chia ra, nhưng các bài con lại giống nhau và cứ bị hỏi đi hỏi lại. Dân thuật toán gọi đó là overlapping subproblems (bài con chồng lấn).

Fibonacci là ví dụ kinh điển. Để tính fib(4), cần fib(3) và fib(2). Nhưng nhánh fib(3) bên trong lại cần fib(2) thêm một lần nữa, và dựng lại nguyên cây con đó từ đầu, dù đáp án vừa được tính xong ở nhánh bên cạnh.

Chỉ với n = 4 đã có 9 lời gọi cho một bài toán chỉ có 5 giá trị phân biệt: fib(2) tính 2 lần, fib(1) tính 3 lần. Với fib(50), có hàng tỷ lần tính trùng, và đó là lý do độ phức tạp là O(2^n).

2.2 Optimal substructure

Nói bằng lời thường: muốn có đáp án tốt nhất của bài lớn, chỉ cần ghép đáp án tốt nhất của các bài con, không phải xét thêm gì khác. Tên gọi là optimal substructure (cấu trúc con tối ưu).

Ví dụ: đường đi ngắn nhất (shortest path) từ A đến C qua B. Nếu A → B → C là đường ngắn nhất từ A đến C, thì A → B phải là đường ngắn nhất từ A đến B, và B → C phải là đường ngắn nhất từ B đến C. Nếu có đường ngắn hơn từ A đến B, thay vào là cải thiện được đường từ 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). Đường dài nhất từ A đến C không nhất thiết đi qua đường dài nhất từ A đến B, vì thêm đoạn B→C có thể buộc đoạn từ A đến B phải ngắn lại để 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 thì kiểm tra cache, nếu đã có đáp án thì 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ỉ tính đúng một lần. Lần đầu thì đệ quy xuống, tính rồi lưu vào memo[k]. Các lần sau chỉ tra cache, mất O(1).

Cache này giống Spring Cache (@Cacheable: tra trước, chưa có mới tính), chỉ khác là key nằm trong tham số hàm.

3.2 Tabulation (bottom-up)

Tabulation (hay bottom-up DP) bỏ hẳn đệ quy. Thay vào đó, bạn điền bảng dp[] từ base case nhỏ nhất lên dần tới đáp án.

-- 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 nên không lo stack overflow. Thứ tự vòng lặp i = 2, 3, ..., n đảm bảo khi tính dp[i] thì cả dp[i-1] và dp[i-2] đã có sẵn.

3.3 So sánh hai cách

Thử ngẫmbạn cần fib(n) với n cỡ 10^6 trong ngôn ngữ có stack giới hạn. Cách nào hỏng trước, vì sao, và đổi sang cách kia thì transition có phải viết lại không?

4. Ví dụ đầy đủ: Fibonacci từ O(2^n) xuống O(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: số lần gọi thật là khoảng 2·fib(51) − 1 ≈ 4×10^10 (2^50 ≈ 10^15 chỉ là chặn trên lỏng). Bản có memo (mục 3.1) chỉ cần cỡ 50 lần tính.

4.2 Nén bộ nhớ xuống O(1)

dp[i] chỉ phụ thuộc dp[i-1] và dp[i-2], nên không cần giữ cả 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)

Chạy tay với n = 5 để thấy hai biến "trượt" dọc dãy (giá trị sau mỗi vòng lặp):

Kết quả prev1 = 5 = fib(5) mà không cần cả mảng.

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. Trước khi code, hãy làm tay trên ví dụ nhỏ để thấy bài con nào cần bài con nào. Bước 1 và 2 thực chất là phân rã bài lớn thành bài con cùng dạng.

Bước 1: xác định state

State (trạng thái) là bộ số nhận diện một bài con, kiểu "đang hỏi về bậc thứ mấy". Nó phải đủ thông tin để tính ra đáp án của bài con đó mà không cần biết bạn đã đến đây bằng đường nào.

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

• Fibonacci: state = n (số thứ tự 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), tức đang xét món đồ thứ i và túi còn chứa được w kg

Bước 2: viết transition

Transition (công thức chuyển trạng thái, còn gọi là recurrence) là công thức biến đáp án của các bài nhỏ hơn thành đáp án của bài đang xét, tức tính dp[state] từ các state đã 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]

-- 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 bài con nhỏ nhất, trả lời thẳng được mà không cần chia nhỏ hơn nữa.

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

-- 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)

Phải đảm bảo khi tính dp[state] thì mọi state nó phụ thuộc đã được tính từ 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 rồi mới đến cột.

Bước 5: nén bộ nhớ (tuỳ chọn)

Nếu transition chỉ phụ thuộc vào vài state gần nhất thì có thể giảm bộ nhớ 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, nên dùng 2 biến thay mảng:
prev2, prev1  -- thay dp[0..n]

Thử ngẫmnếu transition mới là dp[i] = dp[i-1] + dp[i-5], bước 5 phải giữ bao nhiêu biến thay cho cả mảng, và con số đó đọc ra từ đâu trong transition?

6. Bẫy: thiếu base case hoặc sai thứ tự

Bẫy 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)

Bẫy 2: Sai thứ tự tính trong tabulation

-- BUG: điền từ phải sang trái, dp[i-1] và dp[i-2] chưa có giá trị
for i <- n về 2:
    dp[i] <- dp[i-1] + dp[i-2]

-- CORRECT: điền từ base case lên, mỗi ô chỉ dùng các ô đã điền
for i <- 2 đến n:
    dp[i] <- dp[i-1] + dp[i-2]

Quy tắc: hướng của vòng lặp phải ngược chiều với mũi tên phụ thuộc. Có bài hướng này sai, đổi hướng thì đúng (knapsack 1D ở bài 04 là ví dụ điển hình).

Bẫy 3: State không đủ thông tin

Robot đi trên lưới có chướng ngại vật thì state (i, j) là đủ. Thêm ràng buộc "chỉ được dùng tối đa k bước đặc biệt" thì hai tình huống khác nhau bị gộp vào cùng một ô dp.

-- BUG: thiếu k, hai tình huống (đã dùng 0 bước, đã dùng k bước) chung một ô
dp[i][j] <- đường ngắn nhất tới (i, j)

-- CORRECT: k nằm trong state
dp[i][j][k] <- đường ngắn nhất tới (i, j) khi đã dùng k bước đặc biệt

Khi kết quả sai, câu hỏi đầu tiên là: "State đã đủ thông tin chưa?"

Đào sâu

Tóm tắt

• Trước khi viết DP, hỏi hai câu: bài con có lặp lại không, và đáp án bài lớn có ghép được từ đáp án tốt nhất của bài con không.
• Thiết kế theo thứ tự: state, transition, base case, thứ tự tính, nén bộ nhớ.
• Fibonacci là mốc đối chiếu: O(2^n) khi naive, O(n) khi có memo, O(1) bộ nhớ khi chỉ giữ hai biến.

Tự kiểm tra

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