Quy hoạch động là gì: cách hoạt động, code và ví dụ

Quy hoạch động giải bài toán gì

Nhiều bài toán hỏi về cái tốt nhất, rẻ nhất hoặc số cách: ít đồng xu nhất để ra một số tiền, dãy con chung dài nhất của hai chuỗi, tập vật có giá trị lớn nhất bỏ vừa một cái túi, số đường đi qua một lưới. Lời giải đệ quy trực tiếp thường tính lại cùng các trường hợp nhỏ hơn với số lần tăng theo hàm mũ. DP loại bỏ sự lặp lại đó.

Cái tên đến từ Richard Bellman, người phát triển phương pháp này vào thập niên 1950. “Programming” ở đây nghĩa là lập kế hoạch hoặc điền bảng, không phải viết code.

Ý tưởng bằng lời đơn giản

Fibonacci đệ quy ngây thơ cho thấy vấn đề. fib(5) gọi fib(4) và fib(3), rồi fib(4) lại gọi fib(3), và cứ thế: số lần gọi tăng theo hàm mũ. Lưu mỗi kết quả ngay lần đầu tính khiến mọi lần gọi sau đều tức thì.

1. Định nghĩa trạng thái: một bài toán con trông như thế nào? Ví dụ best[a] = số đồng xu ít nhất để ra số tiền a.
2. Viết công thức truy hồi: tính một trạng thái từ các trạng thái nhỏ hơn thế nào? best[a] = 1 + min(best[a - c] for each coin c).
3. Đặt các trường hợp cơ sở: best[0] = 0.
4. Chọn thứ tự tính: từ trên xuống với memoization, hoặc từ dưới lên sao cho các trạng thái nhỏ hơn luôn được điền trước.
5. Đọc đáp án từ trạng thái đúng, và dựng lại lựa chọn thực tế nếu cần.

Từ trên xuống: memoization với functools

Trong Python, functools.cache (Python 3.9+) hoặc functools.lru_cache thêm memoization cho một hàm chỉ bằng một dòng:

from functools import cache

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

print(fib(80))  # 23416728348467685

Không có decorator, fib(80) sẽ thực hiện hơn 10¹⁶ lời gọi đệ quy. Có nó, mỗi giá trị từ 0 đến 80 chỉ được tính một lần.

Ví dụ: đổi tiền xu, từ dưới lên

Các đồng xu 1, 3 và 4; số tiền 6. Cách tham lam lấy 4 trước và cần 4 + 1 + 1 = 3 đồng, nhưng 3 + 3 chỉ dùng 2. DP tìm ra giá trị nhỏ nhất thật sự bằng cách điền best[a] cho a = 0 đến 6:

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

print(min_coins([1, 3, 4], 6))  # 2
print(min_coins([2], 3))        # -1

Ví dụ hai chiều: dãy con chung dài nhất

Nhiều bài toán DP trên hai dãy dùng một lưới: dp[i][j] là đáp án cho i ký tự đầu của chuỗi này và j ký tự đầu của chuỗi kia. Với dãy con chung dài nhất (LCS), nếu hai ký tự khớp thì kéo dài theo đường chéo; nếu không thì lấy kết quả tốt hơn khi bỏ một ký tự của một trong hai chuỗi.

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if 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])
    return dp[len(a)][len(b)]

print(lcs("ABCBDAB", "BDCABA"))  # 4

Một LCS có độ dài 4 là BCBA. Cùng cấu trúc bảng này giải bài khoảng cách chỉnh sửa (edit distance), cách các công cụ diff văn bản đo mức khác nhau giữa hai chuỗi.

Độ phức tạp thời gian và không gian

Quy tắc chung: thời gian = số trạng thái × công việc mỗi trạng thái; không gian = số trạng thái được lưu.

O(n × W) của bài toán cái túi là giả đa thức (pseudo-polynomial): nó phụ thuộc vào giá trị số W, không phải kích thước đầu vào tính bằng bit, nên sẽ chậm khi W rất lớn.

Lỗi thường gặp và khi nào dùng DP

• Sai trạng thái: nếu công thức truy hồi cần thông tin mà trạng thái không chứa (ví dụ vật nào đã dùng rồi), đáp án sẽ sai. Hãy thêm thông tin đó vào trạng thái.
• Sai thứ tự điền: vòng lặp từ dưới lên phải tính mọi trạng thái trước khi nó được đọc.
• Lệch một đơn vị khi chọn kích thước bảng: chuỗi dài n cần n + 1 hàng để bao gồm tiền tố rỗng.
• Đệ quy quá sâu: đệ quy có memoization trên 10.000 trạng thái có thể vượt giới hạn đệ quy của Python; hãy chuyển sang từ dưới lên.
• Đối số không băm được: functools.cache cần đối số băm được (hashable), nên hãy truyền tuple thay vì list.

Ứng dụng điển hình trong phỏng vấn và thực tế: climbing stairs, house robber, dãy con tăng dài nhất, word break, unique paths trên lưới, khoảng cách chỉnh sửa, bài toán cái túi, nhân chuỗi ma trận; trong thực tế còn có gióng hàng chuỗi trong tin sinh học, công cụ diff, kiểm tra chính tả, nhận dạng giọng nói (thuật toán Viterbi) và đường đi ngắn nhất như Bellman-Ford.