Dynamic
Programming

12.1 Dynamic Programming là gì?

Dynamic Programming (DP) = đệ quy + cache để tránh tính lại + định nghĩa rõ "state". Tên "dynamic programming" do Richard Bellman đặt năm 1950 — không liên quan đến "lập trình động" theo nghĩa hiện đại, chỉ là tên gọi lịch sử.

Ví dụ mở đầu — Fibonacci

Đã thấy ở Chương 6:

// Đệ quy ngây thơ — O(2ⁿ)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// Top-down DP (memoization) — O(n)
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

// Bottom-up DP (tabulation) — O(n)
function fibTab(n) {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
  return dp[n];
}

// Optimized — O(n) time, O(1) space
function fibFast(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}

4 phiên bản trên cùng 1 thuật toán, độ phức tạp giảm từ O(2ⁿ) xuống O(n) time, O(1) space.

12.2 Khi nào áp dụng được DP?

Bài toán phải có 2 điều kiện:

1. Optimal Substructure

Lời giải tối ưu của bài lớn được xây dựng từ lời giải tối ưu của các bài con.

Vd: shortest path từ A đến C qua B = shortest path A→B + shortest path B→C.

2. Overlapping Subproblems

Bài con được tính lặp lại nhiều lần khi giải bằng đệ quy thường.

Vd: Fibonacci — fib(3) tính 3 lần khi tính fib(5).

12.3 Top-down: Memoization (Đệ quy + Cache)

Bắt đầu từ bài cần giải, đệ quy đến base case, cache kết quả.

// Template top-down
function solve(state, memo = {}) {
  // 1. Base case
  if (isBase(state)) return baseValue;

  // 2. Đã tính rồi?
  const key = JSON.stringify(state);
  if (memo[key] !== undefined) return memo[key];

  // 3. Tính dựa trên subproblem
  let result = INIT;
  for (const choice of choices) {
    const subResult = solve(nextState(state, choice), memo);
    result = combine(result, subResult, choice);
  }

  return memo[key] = result;
}

Ưu: tự nhiên, dễ viết khi đã có recursion. Chỉ tính state thật sự cần.

Nhược: tốn stack (đệ quy sâu), JSON.stringify chậm.

12.4 Bottom-up: Tabulation (DP table)

Bắt đầu từ base case, tính dần các state lớn hơn, lưu vào bảng.

// Template bottom-up
function solve(input) {
  const dp = new Array(n + 1);

  // 1. Base case
  dp[0] = baseValue;

  // 2. Điền bảng theo thứ tự đúng
  for (let i = 1; i <= n; i++) {
    dp[i] = INIT;
    for (const choice of choices) {
      dp[i] = combine(dp[i], dp[prevState(i, choice)]);
    }
  }

  return dp[n];
}

Ưu: không tốn stack, thường nhanh hơn (no function call overhead).

Nhược: phải xác định đúng thứ tự duyệt; có thể tính những state không cần.

Top-down vs Bottom-up — chọn cái nào?

• Bài có nhiều state KHÔNG cần thiết → Top-down ưu thế (chỉ tính state cần)
• Bài có thứ tự duyệt hiển nhiên (vd 1D từ trái phải) → Bottom-up đẹp hơn
• State key phức tạp (object, set) → Top-down dễ hơn (memo Map)
• Cần tối ưu space → Bottom-up dễ rolling array

12.5 Quy trình giải bài DP — 5 bước

Áp dụng cho Fibonacci

1. State: dp[i] = số Fibonacci thứ i
2. Base: dp[0]=0, dp[1]=1
3. Transition: dp[i] = dp[i-1] + dp[i-2]
4. Thứ tự: từ i=2 đến n
5. Đáp án: dp[n]

12.6 1D Linear DP — bắt đầu từ đây

12.6.1 Climbing Stairs

n bậc thang, mỗi bước nhảy 1 hoặc 2. Đếm số cách lên đỉnh.

// State: dp[i] = số cách lên bậc i
// Transition: dp[i] = dp[i-1] + dp[i-2]  (đến từ bậc i-1 nhảy 1, hoặc bậc i-2 nhảy 2)
// Base: dp[0] = 1, dp[1] = 1
function climbStairs(n) {
  if (n <= 1) return 1;
  let a = 1, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}

12.6.2 House Robber

Mảng tiền các nhà. Không được trộm 2 nhà liền kề. Tối đa lấy được bao nhiêu?

// State: dp[i] = max tiền trộm được khi xét đến nhà i
// Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
//             (bỏ qua nhà i, hoặc trộm nhà i + best của (i-2))
function rob(nums) {
  let prev2 = 0, prev1 = 0;
  for (const n of nums) {
    [prev2, prev1] = [prev1, Math.max(prev1, prev2 + n)];
  }
  return prev1;
}

12.6.3 Coin Change

Cho coins và amount. Tìm số ít nhất coin để tổng = amount. Trả -1 nếu không thể.

// State: dp[i] = số coin ít nhất để tạo amount i
// Transition: dp[i] = min(dp[i - c] + 1) cho mọi coin c <= i
// Base: dp[0] = 0
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

12.6.4 Word Break

Cho string s và wordDict. Có thể chia s thành các word từ dict không?

// State: dp[i] = s[0..i] có chia được không?
// Transition: dp[i] = true nếu tồn tại j sao cho dp[j] = true VÀ s[j..i] ∈ dict
function wordBreak(s, wordDict) {
  const set = new Set(wordDict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && set.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

12.7 2D Grid DP

12.7.1 Unique Paths

Lưới m×n. Robot đi từ trái-trên đến phải-dưới, chỉ xuống hoặc phải. Đếm số đường.

// State: dp[i][j] = số đường đến ô (i, j)
// Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1]
// Base: hàng đầu và cột đầu = 1
function uniquePaths(m, n) {
  const dp = Array.from({length: m}, () => new Array(n).fill(1));
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
  return dp[m-1][n-1];
}

12.7.2 Minimum Path Sum

function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({length: m}, () => new Array(n));
  dp[0][0] = grid[0][0];
  for (let i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
  for (let j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    }
  }
  return dp[m-1][n-1];
}

12.8 Knapsack — bài "ba lô"

0/1 Knapsack — mỗi item dùng 1 lần

Có n item với weight và value. Túi chở tối đa W. Lấy items để max tổng value.

// State: dp[i][w] = max value khi xét i item đầu, túi capacity w
// Transition:
//   - Không lấy item i:    dp[i-1][w]
//   - Lấy item i (nếu w >= weights[i-1]):  dp[i-1][w - weights[i-1]] + values[i-1]
// dp[i][w] = max của 2 lựa chọn

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

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i-1][w];  // không lấy
      if (w >= weights[i-1]) {
        dp[i][w] = Math.max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
      }
    }
  }
  return dp[n][W];
}

Unbounded Knapsack — item dùng nhiều lần

// Khác 0/1: khi "lấy item i", state vẫn ở i (chưa chuyển sang i-1)
function knapsackUnbounded(weights, values, W) {
  const dp = new Array(W + 1).fill(0);
  for (let w = 0; w <= W; w++) {
    for (let i = 0; i < weights.length; i++) {
      if (weights[i] <= w) {
        dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
      }
    }
  }
  return dp[W];
}

Bài: Partition Equal Subset Sum

Cho mảng. Có thể chia thành 2 subset có tổng bằng nhau? → 0/1 Knapsack tìm subset có tổng = sum/2.

12.9 LIS & LCS — 2 bài DP "phải biết"

12.9.1 Longest Increasing Subsequence (LIS)

// O(n²) DP
// State: dp[i] = độ dài LIS kết thúc tại index i
// Transition: dp[i] = max(dp[j] + 1) cho mọi j < i với arr[j] < arr[i]
function lisN2(arr) {
  const dp = new Array(arr.length).fill(1);
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  return Math.max(...dp);
}

// O(n log n) bằng patience sorting + binary search
function lisNlogN(arr) {
  const tails = [];
  for (const x of arr) {
    // Lower bound binary search
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x;
  }
  return tails.length;
}

12.9.2 Longest Common Subsequence (LCS)

// LCS giữa 2 string a, b
// State: dp[i][j] = LCS của a[0..i-1] và b[0..j-1]
// Transition:
//   - 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])
function lcs(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 = 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] + 1;
      else                   dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m][n];
}

// "abcde", "ace" → LCS = "ace" (length 3)

12.9.3 Edit Distance (Levenshtein)

// Số phép biến đổi tối thiểu (insert, delete, replace) để word1 → word2
function minDistance(w1, w2) {
  const m = w1.length, n = w2.length;
  const dp = Array.from({length: m + 1}, () => new Array(n + 1));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (w1[i-1] === w2[j-1]) dp[i][j] = dp[i-1][j-1];
      else dp[i][j] = 1 + Math.min(dp[i-1][j],     // delete
                                    dp[i][j-1],     // insert
                                    dp[i-1][j-1]);  // replace
    }
  }
  return dp[m][n];
}

12.10 Interval DP — DP trên đoạn

State dp[i][j] = đáp án cho đoạn từ i đến j. Duyệt theo độ dài đoạn từ nhỏ đến lớn.

Bài: Matrix Chain Multiplication

// Cho dimensions p[0..n], tìm cách "đặt ngoặc" để tối thiểu phép nhân khi nhân chuỗi ma trận
function matrixChain(p) {
  const n = p.length - 1;
  const dp = Array.from({length: n}, () => new Array(n).fill(0));

  // Duyệt theo độ dài đoạn (l = 2 đến n)
  for (let l = 2; l <= n; l++) {
    for (let i = 0; i <= n - l; i++) {
      const j = i + l - 1;
      dp[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        const cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1];
        if (cost < dp[i][j]) dp[i][j] = cost;
      }
    }
  }
  return dp[0][n-1];
}

12.11 Tối ưu Space — Rolling Array

Nhiều bài DP chỉ cần dp[i-1] (hoặc i-2) để tính dp[i] → có thể tối ưu O(n) → O(1).

// Knapsack 0/1 — O(n × W) space
// Tối ưu xuống O(W) bằng cách duyệt w từ phải sang trái
function knapsack01Optim(weights, values, W) {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = W; w >= weights[i]; w--) {  // ngược chiều!
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}

// Tại sao duyệt ngược?
// Nếu duyệt xuôi, dp[w - weights[i]] đã được update với item i hiện tại → trùng item.
// Duyệt ngược đảm bảo dp[w - weights[i]] còn là từ vòng (i-1).

LCS, Climbing Stairs, House Robber, Min Path Sum đều có thể tối ưu space.

Bài tập

Tổng kết chương 12 — và toàn bộ giáo trình

• ✅ DP = đệ quy + cache + tư duy state
• ✅ 2 điều kiện: optimal substructure + overlapping subproblems
• ✅ Top-down (memo) vs Bottom-up (tabulation) — đánh đổi
• ✅ Quy trình 5 bước: state → base → transition → thứ tự duyệt → đáp án
• ✅ 5 dạng DP phổ biến: 1D linear, 2D grid, knapsack, LIS/LCS, interval
• ✅ Tối ưu space bằng rolling array khi state chỉ phụ thuộc 1-2 vòng trước