Dynamic programming (DP) giải các bài toán có bài toán con chồng lấn (overlapping subproblems) và optimal substructure bằng cách tính mỗi bài toán con một lần và tái sử dụng kết quả. Hai phong cách là memoization (top-down) và tabulation (bottom-up).
Đệ quy thô sơ tính lại cùng các bài toán con theo cấp số mũ. DP lưu đệm chúng, thu gọn khối lượng công việc hàm mũ thành đa thức.
from functools import lru_cache
@lru_cache(maxsize=None) # tự động lưu đệm kết quả
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # mỗi n được tính một lần
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # xây dựng từ các base case
return dp[n]
| Memoization | Tabulation | |
|---|---|---|
| Hướng | đệ quy top-down | lặp bottom-up |
| Tính | chỉ các trạng thái cần thiết | tất cả các trạng thái |
| Rủi ro | tràn stack | không có |
| Bộ nhớ | có thể cắt giảm | thường giảm được xuống O(1) hàng |
Fibonacci: từ O(2ⁿ) thô sơ xuống O(n) thời gian, O(n) (hoặc O(1)) bộ nhớ.
Dùng DP khi các bài toán con chồng lấn. Định nghĩa trạng thái và hệ thức truy hồi một cách cẩn thận — đó là phần khó. Nếu các bài toán con không chồng lấn, divide-and-conquer thuần túy là đủ.
DP biến các bài toán hàm mũ bất khả thi — đường đi ngắn nhất, khoảng cách chỉnh sửa (edit distance), bài toán cái túi (knapsack) — thành các bài toán hiệu quả.
Kỹ năng xác định trạng thái và hệ thức truy hồi nằm trong số những kỹ năng được coi trọng nhất trong phỏng vấn thuật toán.
Nó là nền tảng của các hệ thống thực tế từ công cụ diff đến căn chỉnh chuỗi (sequence alignment) trong tin sinh học.