🔢 Algorithms✍️ Khoa📅 19/04/2026☕ 7 phút đọc

Algorithms: Dynamic Programming

1. Khi nào dùng DP?

Hai điều kiện bắt buộc:

  1. Optimal Substructure: optimal solution của bài lớn được xây từ optimal solution của bài con
  2. Overlapping Subproblems: cùng subproblem được giải nhiều lần

Dấu hiệu nhận biết:

  • "Tối ưu" (min/max/count/exists)
  • Chia bài thành các bài con nhỏ hơn
  • Câu hỏi về subsequence, substring, partition, knapsack
  • "Bao nhiêu cách...", "Có thể không..."

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

flowchart LR
  subgraph TD1["Top-down (Memoization)"]
    F5["fib(5)"] --> F4["fib(4)"]
    F5 --> F3h["fib(3) ✓ hit cache"]
    F4 --> F3["fib(3) ✓ memo"]
    F4 --> F2["fib(2) ✓ memo"]
  end

  subgraph BU["Bottom-up (Tabulation)"]
    B0["dp[0]=0"] --> B1["dp[1]=1"] --> B2["dp[2]=1"] --> B3["dp[3]=2"] --> B4["dp[4]=3"] --> B5["dp[5]=5"]
  end
Top-down:                    Bottom-up:
fib(5)                       dp[0]=0
├── fib(4)                   dp[1]=1
│   ├── fib(3) ✓ memo        dp[2]=1
│   └── fib(2) ✓ memo        dp[3]=2
└── fib(3) ✓ hit cache       dp[4]=3
                             dp[5]=5
Top-down Bottom-up
Code Dễ viết, đệ quy tự nhiên Phức tạp hơn, iterative
Space Stack + memo Chỉ dp table
Subproblems Chỉ tính khi cần Tính tất cả
Khi dùng Draft nhanh, sparse subproblems Production, space-optimize được

Top-down template

func solve(n int) int {
    memo := make(map[int]int)
    var dp func(i int) int
    dp = func(i int) int {
        if i <= 1 { return i } // base case
        if v, ok := memo[i]; ok { return v }
        result := dp(i-1) + dp(i-2)
        memo[i] = result
        return result
    }
    return dp(n)
}

Bottom-up template

func solve(n int) int {
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 1 // base cases
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2] // transition
    }
    return dp[n]
}

3. Thiết kế State Transition

Ba bước:

  1. Define state: dp[i] = "..."
  2. Base case: giá trị ban đầu
  3. Transition: dp[i] tính từ các dp[j] trước

4. Bài kinh điển

Coin Change (Unbounded Knapsack)

coins = [1, 5, 11], amount = 15
dp[0] = 0
dp[1] = dp[0]+1 = 1  (coin 1)
dp[5] = dp[0]+1 = 1  (coin 5)
dp[11] = 1           (coin 11)
dp[15] = dp[4]+1 = ?  min over all coins
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1 // infinity
    }
    dp[0] = 0

    for i := 1; i <= amount; i++ {
        for _, coin := range coins {
            if coin <= i {
                if dp[i-coin]+1 < dp[i] {
                    dp[i] = dp[i-coin] + 1
                }
            }
        }
    }

    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

0/1 Knapsack

Chọn items (weight, value) với tổng weight <= capacity, maximize value.

items: [(w=1,v=1), (w=3,v=4), (w=4,v=5), (w=5,v=7)]
capacity = 7

dp[i][w] = max value dùng i items đầu, capacity w
func knapsack(weights, values []int, cap int) int {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, cap+1)
    }

    for i := 1; i <= n; i++ {
        for w := 0; w <= cap; w++ {
            // Không lấy item i
            dp[i][w] = dp[i-1][w]
            // Lấy item i (nếu đủ weight)
            if weights[i-1] <= w {
                take := dp[i-1][w-weights[i-1]] + values[i-1]
                if take > dp[i][w] {
                    dp[i][w] = take
                }
            }
        }
    }
    return dp[n][cap]
}

// Space-optimized: 1D dp (duyệt ngược)
func knapsack1D(weights, values []int, cap int) int {
    dp := make([]int, cap+1)
    for i := 0; i < len(weights); i++ {
        for w := cap; w >= weights[i]; w-- { // duyệt ngược!
            if dp[w-weights[i]]+values[i] > dp[w] {
                dp[w] = dp[w-weights[i]] + values[i]
            }
        }
    }
    return dp[cap]
}

Tại sao duyệt ngược? Để đảm bảo mỗi item chỉ dùng 1 lần — nếu duyệt xuôi, dp[w] có thể dùng item i nhiều lần.

Longest Common Subsequence (LCS)

s1 = "abcde", s2 = "ace"
LCS = "ace", length = 3

dp[i][j] = LCS của s1[0..i-1] và s2[0..j-1]
func longestCommonSubsequence(text1, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}

Longest Increasing Subsequence (LIS)

nums = [10, 9, 2, 5, 3, 7, 101, 18]
LIS = [2, 3, 7, 18] hay [2, 5, 7, 101], length = 4
// O(n²) — DP rõ ràng
func lisDP(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp { dp[i] = 1 }
    best := 1
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] && dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
            }
        }
        if dp[i] > best { best = dp[i] }
    }
    return best
}

// O(n log n) — Patience sorting + binary search
func lisOptimal(nums []int) int {
    tails := []int{}
    for _, num := range nums {
        // Tìm vị trí insert trong tails
        pos := sort.SearchInts(tails, num)
        if pos == len(tails) {
            tails = append(tails, num)
        } else {
            tails[pos] = num
        }
    }
    return len(tails)
}

Edit Distance

word1 = "horse", word2 = "ros"
Operations: insert, delete, replace

dp[i][j] = min operations để convert word1[0..i-1] → word2[0..j-1]
func minDistance(word1, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        dp[i][0] = i // delete i chars
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j // insert j chars
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1] // no op
            } else {
                dp[i][j] = 1 + min(
                    dp[i-1][j],   // delete
                    dp[i][j-1],   // insert
                    dp[i-1][j-1], // replace
                )
            }
        }
    }
    return dp[m][n]
}

5. Các dạng DP phổ biến

Dạng Ví dụ State điển hình
1D linear Fibonacci, Climbing Stairs dp[i]
2D grid Unique Paths, Minimum Path Sum dp[i][j]
Subsequence LCS, LIS, Edit Distance dp[i][j] với 2 strings
Knapsack Coin Change, Subset Sum dp[i][w]
Interval Matrix Chain, Burst Balloons dp[i][j] interval
State machine Stock prices với cooldown dp[i][state]

Stock với cooldown (State Machine DP)

States: held, sold, rest
Transitions:
  held → held (do nothing)
  held → sold (sell)
  sold → rest (cooldown)
  rest → held (buy)
  rest → rest (do nothing)
func maxProfit(prices []int) int {
    held := -prices[0]
    sold, rest := 0, 0
    for i := 1; i < len(prices); i++ {
        prevHeld, prevSold, prevRest := held, sold, rest
        held = max(prevHeld, prevRest-prices[i])
        sold = prevHeld + prices[i]
        rest = max(prevRest, prevSold)
    }
    return max(sold, rest)
}

6. Common mistakes

Lỗi Fix
Define state mơ hồ Viết rõ: dp[i] = max profit khi xét i coins đầu tiên
Quên base case Luôn khởi tạo dp[0] và dp[1] trước
Index off-by-one Dùng i cho item thứ i, i-1 để access array
Không nhận ra 2D có thể compress xuống 1D Khi dp[i][j] chỉ dùng dp[i-1][...] → compress được
Thứ tự loop sai trong knapsack 0/1 knapsack: duyệt ngược. Unbounded: duyệt xuôi

💡 Interview: Bắt đầu bằng brute force đệ quy, rồi thêm memoization (top-down), rồi convert sang bottom-up nếu cần. Nói rõ "optimal substructure" và "overlapping subproblems" để show hiểu bản chất.