Quy hoạch động (Dynamic Programming — DP) giải bài toán bằng cách chia thành các bài toán con chồng lặp và lưu lại kết quả để tránh tính lại.
Hai tính chất cần có
- Optimal substructure: Đáp án tối ưu của bài toán lớn được xây dựng từ đáp án tối ưu của bài toán con.
- Overlapping subproblems: Các bài toán con bị lặp lại nhiều lần.
Hai cách cài đặt DP
Top-down (Memoization — đệ quy + ghi nhớ)
map<int, long long> memo;
long long dp(int n) {
if (n <= 1) return n;
if (memo.count(n)) return memo[n];
return memo[n] = dp(n-1) + dp(n-2);
}
Bottom-up (Tabulation — lặp)
vector<long long> dp(n+1);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i-1] + dp[i-2];
Ví dụ 1: Dãy con tăng dài nhất (LIS)
Tìm dãy con tăng dần dài nhất trong mảng .
:
vector<int> dp(n, 1);
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (a[j] < a[i]) dp[i] = max(dp[i], dp[j]+1);
cout << *max_element(dp.begin(), dp.end());
— dùng binary search:
vector<int> lis;
for (int x : a) {
auto it = lower_bound(lis.begin(), lis.end(), x);
if (it == lis.end()) lis.push_back(x);
else *it = x;
}
cout << lis.size();
Ví dụ 2: Bài toán cái túi 0/1 (0/1 Knapsack)
Chọn các vật có trọng lượng và giá trị sao cho tổng trọng lượng và tổng giá trị lớn nhất.
// dp[j] = giá trị lớn nhất với sức chứa j
vector<int> dp(W+1, 0);
for (int i = 0; i < n; i++)
for (int j = W; j >= w[i]; j--) // duyệt ngược để không dùng vật i 2 lần
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
cout << dp[W];
dp = [0] * (W + 1)
for i in range(n):
for j in range(W, w[i]-1, -1):
dp[j] = max(dp[j], dp[j-w[i]] + v[i])
print(dp[W])
Ví dụ 3: Dãy con chung dài nhất (LCS)
Tìm dãy con chung dài nhất của hai chuỗi và .
int n = s.size(), m = t.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
cout << dp[n][m];
Ví dụ 4: DP trên đồ thị — Đường đi dài nhất trên DAG
// Topo sort + DP
vector<int> order; // thứ tự topo
vector<long long> dp(n, 0);
for (int u : order)
for (auto [v, w] : adj[u])
dp[v] = max(dp[v], dp[u] + w);
Các dạng DP phổ biến
| Dạng | Ví dụ |
|---|---|
| DP 1D | Fibonacci, coin change |
| DP 2D | LCS, edit distance |
| DP bitmask | Traveling Salesman Problem |
| DP trên cây | Diameter, independent set |
| DP chia để trị | Convex hull trick |
Mẹo
- Xác định trạng thái (state): dp[i] có nghĩa là gì?
- Xác định công thức chuyển (transition): dp[i] tính từ dp[j] nào?
- Xác định base case: giá trị khởi tạo.
- Xác định thứ tự tính: tính dp[i] trước dp[j] hay sau?
Bình luận