💡 Quy hoạch động

Thử tính số Fibonacci bằng đệ quy thuần túy - hàm tự gọi lại chính nó theo công thức fib(n) = fib(n-1) + fib(n-2):

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

Trông rất gọn, nhưng thử chạy fib(40) sẽ thấy máy “treo” vài giây. Vấn đề nằm ở chỗ: để tính fib(5), hàm gọi fib(4) và fib(3); nhưng fib(4) lại tự gọi fib(3) một lần nữa - fib(3) bị tính đi tính lại! Vẽ cây gọi hàm ra sẽ thấy số lượng lời gọi trùng lặp bùng nổ theo cấp số nhân, cho độ phức tạp O(2ⁿ) - dù đáp số cuối cùng chỉ có n+1 giá trị khác nhau (fib(0) đến fib(n)) cần tính.

Quy hoạch động (Dynamic Programming - DP) giải quyết đúng sự lãng phí này bằng một ý tưởng cực đơn giản: kết quả nào đã tính rồi thì lưu lại, lần sau cần thì tra ra dùng ngay, không tính lại.

Hai cách nhớ kết quả: từ trên xuống và từ dưới lên

Cách 1 - Memoization (nhớ lại, từ trên xuống - top-down): giữ nguyên code đệ quy, chỉ thêm một “bộ nhớ đệm” (cache) để lưu kết quả đã tính.

def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n in memo:            # đã tính trước đó -> tra ra dùng luôn
        return memo[n]
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Cách 2 - Tabulation (xây bảng, từ dưới lên - bottom-up): bỏ hẳn đệ quy, tính từ những giá trị nhỏ nhất rồi dùng vòng lặp xây dần lên giá trị cần tìm - giống cách bạn tự tính Fibonacci bằng tay: viết 0, 1, rồi cộng liên tiếp.

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Cả hai cách đều đưa độ phức tạp từ O(2ⁿ) xuống O(n) - vì mỗi giá trị fib(i) giờ chỉ được tính đúng một lần. Khác biệt chỉ nằm ở hướng đi: memoization đi từ bài toán lớn xuống bài toán nhỏ (rồi quay lên khi trả kết quả), tabulation đi thẳng từ bài toán nhỏ lên bài toán lớn, không cần đệ quy nên cũng tiết kiệm bộ nhớ ngăn xếp hơn.

Mẹo

Trong thực hành, dp[i] thường chỉ phụ thuộc vào vài giá trị liền trước (ở Fibonacci là dp[i-1] và dp[i-2]), nên có thể bỏ hẳn mảng dp, chỉ giữ 2 biến cuộn (rolling variables) để giảm bộ nhớ từ O(n) xuống O(1). Đây gọi là kỹ thuật “tối ưu không gian” (space optimization), rất phổ biến khi cài DP cho production.

Khi nào một bài toán giải được bằng DP?

Không phải bài toán đệ quy nào cũng cần DP. Hai dấu hiệu nhận biết:

1. Bài toán con chồng chéo (overlapping subproblems): nếu giải bằng đệ quy thuần túy, cùng một bài toán con bị gọi lại nhiều lần (như fib(3) ở trên). Nếu mỗi bài toán con chỉ được gọi đúng một lần, lưu kết quả không giúp ích gì - đó là dấu hiệu của chia để trị chứ không phải DP (Merge Sort chia mảng thành 2 nửa hoàn toàn tách biệt, không nửa nào lặp lại).
2. Cấu trúc con tối ưu (optimal substructure): nghiệm tối ưu của bài toán lớn có thể ghép từ nghiệm tối ưu của các bài toán con nhỏ hơn. Nếu tính chất này không đúng, giải bài toán con tối ưu không giúp bạn xây được bài toán lớn tối ưu.

Khi cả hai điều kiện trên đều thỏa, quy trình chung để giải một bài toán DP là: xác định trạng thái (state - “bài toán con được tham số hóa bằng gì”), viết ra công thức truy hồi (state transition - trạng thái lớn liên hệ thế nào với các trạng thái nhỏ hơn), xác định điều kiện biên (base case), rồi chọn cài bằng memoization hoặc tabulation.

Coin Change - đổi tiền với số xu tối thiểu

Cho các loại tiền xu coins (mỗi loại dùng không giới hạn số lần) và một số tiền amount, tìm số xu tối thiểu để đủ số tiền đó.

Gọi dp[i] là số xu tối thiểu để đủ số tiền i. Với mỗi đồng xu coin có thể dùng ở bước cuối, bài toán con còn lại là đủ số tiền i - coin, nên:

dp[i] = min(dp[i - coin] + 1)  với mọi coin <= i
dp[0] = 0  (điều kiện biên: 0 đồng không cần xu nào)

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Bài toán cái túi 0/1 (0-1 Knapsack)

Cho n món đồ, mỗi món có trọng lượng weight[i] và giá trị value[i], và một cái túi sức chứa capacity. Mỗi món chỉ được chọn tối đa 1 lần (“0 hoặc 1” - tên gọi 0-1 Knapsack). Chọn tập món sao cho tổng giá trị lớn nhất mà không vượt sức chứa.

Gọi dp[i][c] là giá trị lớn nhất khi chỉ xét i món đầu tiên với sức chứa c. Với món thứ i, có đúng 2 lựa chọn: bỏ qua nó (dp[i-1][c], giữ nguyên sức chứa) hoặc lấy nó nếu còn đủ chỗ (dp[i-1][c - weight[i]] + value[i], giảm sức chứa và cộng giá trị) - chọn phương án nào cho giá trị lớn hơn:

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]                          # bỏ qua món i
            if weights[i - 1] <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - weights[i - 1]] + values[i - 1])  # lấy món i
    return dp[n][capacity]

Biến thể: cái túi không giới hạn (Unbounded Knapsack)

Giống hệt bài toán trên, nhưng mỗi món giờ được chọn không giới hạn số lần (miễn còn đủ chỗ). Chỉ một chữ khác trong công thức: khi lấy món i, ta cho phép lấy lại chính món đó thêm lần nữa, nên tham chiếu dp[i][...] (cùng hàng, vì món i vẫn còn “được phép chọn tiếp”) thay vì dp[i-1][...]:

def unbounded_knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]
            if weights[i - 1] <= c:
                dp[i][c] = max(dp[i][c], dp[i][c - weights[i - 1]] + values[i - 1])  # dp[i], không phải dp[i-1]
    return dp[n][capacity]

Mẹo

coin_change ở trên thực chất là một dạng Unbounded Knapsack - mỗi loại xu được dùng không giới hạn số lần, chỉ đổi mục tiêu từ “tối đa hóa giá trị” sang “tối thiểu hóa số xu”.

Khoảng cách chỉnh sửa (Edit Distance)

Cho hai chuỗi s và t, tìm số bước chỉnh sửa tối thiểu (thêm, xóa, hoặc thay 1 ký tự) để biến s thành t. Đây là bài toán nền tảng đằng sau tính năng “gợi ý sửa lỗi chính tả” hay diff giữa hai phiên bản văn bản.

Gọi dp[i][j] là số bước tối thiểu để biến i ký tự đầu của s thành j ký tự đầu của t. Xét ký tự cuối cùng của mỗi tiền tố:

• Nếu s[i-1] == t[j-1], hai ký tự đã khớp nhau, không cần sửa gì thêm ở bước này: dp[i][j] = dp[i-1][j-1].
• Nếu khác nhau, ta chọn phương án rẻ nhất trong ba khả năng rồi cộng thêm 1 bước sửa:
  • Thay ký tự cuối của s thành ký tự cuối của t: dp[i-1][j-1] + 1
  • Xóa ký tự cuối của s: dp[i-1][j] + 1
  • Thêm ký tự cuối của t vào s: dp[i][j-1] + 1

Điều kiện biên: biến chuỗi rỗng thành chuỗi có k ký tự (hoặc ngược lại) luôn cần đúng k bước, nên dp[0][j] = j và dp[i][0] = i.

Python

def edit_distance(s, t):
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],  # thay
                    dp[i - 1][j],      # xóa
                    dp[i][j - 1],      # thêm
                )

    return dp[n][m]

Kotlin

fun editDistance(s: String, t: String): Int {
    val n = s.length
    val m = t.length
    val dp = Array(n + 1) { IntArray(m + 1) }

    for (i in 0..n) dp[i][0] = i
    for (j in 0..m) dp[0][j] = j

    for (i in 1..n) {
        for (j in 1..m) {
            dp[i][j] = if (s[i - 1] == t[j - 1]) {
                dp[i - 1][j - 1]
            } else {
                1 + minOf(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
            }
        }
    }
    return dp[n][m]
}

Ghi chú

Độ phức tạp thời gian và không gian đều là O(n × m), vì bảng dp có kích thước (n+1) × (m+1) và mỗi ô chỉ mất O(1) để tính.