Bài 7: Quy Hoạch Động Trực Quan — Edit Distance & Knapsack

Ở Bài 6 chúng ta tăng tốc truy vấn bằng cách lưu sẵn kết quả ở các node cây. Quy hoạch động (Dynamic Programming — DP) áp dụng đúng ý tưởng "lưu sẵn để khỏi tính lại" đó, nhưng theo một cách tổng quát hơn nhiều — biến hàng loạt bài toán tưởng chừng cần thời gian mũ (exponential) thành đa thức (polynomial).

1. Quy hoạch động là gì? Hai điều kiện bắt buộc

Một bài toán phù hợp với DP cần 2 tính chất: bài toán con chồng lấp (overlapping subproblems — cùng một bài toán con được giải đi giải lại nhiều lần) và cấu trúc con tối ưu (optimal substructure — lời giải tối ưu của bài lớn được xây từ lời giải tối ưu của các bài con). Ví dụ kinh điển: tính Fibonacci bằng đệ quy thuần rất chậm vì tính lại cùng giá trị hàng ngàn lần:

// Đệ quy thuần — O(2^n), tính lại fib(3) tới hàng chục lần khi n lớn!
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}
// fibNaive(40) đã mất vài giây — fib(3) được tính lại hơn 300.000 lần

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

Có 2 cách cài DP: Memoization giữ nguyên đệ quy nhưng thêm bộ nhớ đệm (cache) tránh tính lại; Tabulation bỏ đệ quy hẳn, xây bảng kết quả từ dưới lên theo thứ tự tăng dần:

// Memoization (Top-down) — O(n), vẫn đệ quy nhưng cache kết quả
function fibMemo(n, cache = new Map()) {
  if (n <= 1) return n;
  if (cache.has(n)) return cache.get(n); // đã tính rồi — trả về ngay
  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  cache.set(n, result);
  return result;
}

// Tabulation (Bottom-up) — O(n), không đệ quy, không tốn stack
function fibTabulation(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

3. Bài toán kinh điển: Edit Distance (Khoảng cách chỉnh sửa)

Edit Distance (khoảng cách Levenshtein) đo số thao tác tối thiểu — thêm, xoá, hoặc thay thế 1 ký tự — để biến chuỗi A thành chuỗi B. Đây chính là thuật toán đứng sau git diff, gợi ý chính tả, và so khớp trình tự DNA. Công thức truy hồi:

function editDistance(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 0; i <= m; i++) dp[i][0] = i; // xoá hết i ký tự của a
  for (let j = 0; j <= n; j++) dp[0][j] = j; // thêm hết j ký tự của b

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // ký tự khớp — không tốn thao tác
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],   // xoá ký tự a[i-1]
          dp[i][j - 1],   // thêm ký tự b[j-1]
          dp[i - 1][j - 1] // thay thế a[i-1] bằng b[j-1]
        );
      }
    }
  }
  return dp[m][n];
}

4. Bài toán kinh điển: 0/1 Knapsack (Bài toán cái túi)

Cho $n$ món đồ, mỗi món có trọng lượng $w_i$ và giá trị $v_i$, và một cái túi chỉ chứa được tối đa trọng lượng $W$. Chọn tập món đồ nào để tổng giá trị lớn nhất mà không vượt quá $W$ — mỗi món chỉ được chọn 0 hoặc 1 lần (không được chọn phần lẻ, khác với "Fractional Knapsack" giải được bằng Greedy):

function knapsack01(items, capacity) {
  const n = items.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const { weight, value } = items[i - 1];
    for (let w = 0; w <= capacity; w++) {
      if (weight > w) {
        dp[i][w] = dp[i - 1][w]; // món này không nhét vừa — bỏ qua
      } else {
        dp[i][w] = Math.max(
          dp[i - 1][w],                    // KHÔNG chọn món i
          dp[i - 1][w - weight] + value    // CÓ chọn món i
        );
      }
    }
  }
  return dp[n][capacity];
}

5. So sánh Quy hoạch động, Đệ quy thuần và Greedy

Sân chơi tương tác: Edit Distance Visualizer

Nhập 2 chuỗi rồi bấm "Tính toán" để xem bảng DP lấp đầy từng ô, kèm đường truy vết (traceback) màu vàng cho biết chính xác chuỗi thao tác (thêm/xoá/thay thế) để biến chuỗi A thành chuỗi B.