Quy hoạch động (DP)

Wiki › Thuật toán

huunguyen · Last updated 3, Tháng 4, 2026, 20:31

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.

Nếu thiếu một trong hai, DP không áp dụng được (dùng Greedy hoặc Divide & Conquer thay thế).

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);
}

Ưu điểm: Chỉ tính các trạng thái thực sự cần thiết, dễ cài khi transition phức tạp.

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];

Ưu điểm: Không có overhead đệ quy, dễ tối ưu bộ nhớ (rolling array).

Quy trình thiết kế DP

Xác định trạng thái — dp[i] có nghĩa là gì?
Xác định công thức chuyển — 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?
Xác định kết quả — lấy dp[n], max(dp), hay tổng hợp gì?

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 $a$ .

$O (N^{2})$ :

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());

$O (N \log N)$ — 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 $w_{i}$ và giá trị $v_{i}$ sao cho tổng trọng lượng $\leq W$ và tổng giá trị lớn nhất.

vector<int> dp(W+1, 0);
for (int i = 0; i < n; i++)
    for (int j = W; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
cout << dp[W];

Unbounded Knapsack (dùng mỗi vật không giới hạn lần):

for (int i = 0; i < n; i++)
    for (int j = w[i]; j <= W; j++)
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);

Ví dụ 3: Dãy con chung dài nhất (LCS)

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: Edit Distance

vector<vector<int>> dp(n+1, vector<int>(m+1));
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
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];
        else dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
cout << dp[n][m];

Các dạng DP — trang chi tiết

Dạng	Mô tả	Trang
DP khoảng	`dp[l][r]` trên đoạn $[l, r]$	DP khoảng
DP bitmask	Trạng thái là tập con bitmask	DP bitmask
DP broken profile	Lát lưới theo từng ô với bitmask	DP broken profile
DP trên cây	Trạng thái là nút cây, DFS	DP trên cây
DP trên đồ thị	DAG, SCC, Dijkstra + DP	DP trên đồ thị
DP chữ số	Xây số theo từng chữ số	DP chữ số
DP xác suất	Trạng thái là xác suất / kỳ vọng	DP xác suất
DP nhân ma trận	Truy hồi tuyến tính với $N \leq 10^{18}$	DP nhân ma trận
DP tối ưu hóa	CHT, D&C DP, Knuth	DP tối ưu hóa

Tối ưu bộ nhớ: Rolling Array

Khi dp[i] chỉ phụ thuộc dp[i-1], dùng 2 mảng thay vì $N$ mảng:

vector<vector<int>> dp(2, vector<int>(m+1, 0));
for (int i = 1; i <= n; i++) {
    int cur = i & 1, prev = 1 - cur;
    for (int j = 1; j <= m; j++)
        dp[cur][j] = ...dp[prev][...];
}

Phân biệt DP với các kỹ thuật khác

Kỹ thuật	Khi nào dùng
DP	Bài toán con chồng lặp, cần tối ưu hoặc đếm
Greedy	Chọn tham lam tại mỗi bước luôn dẫn đến tối ưu toàn cục
Divide & Conquer	Bài toán con độc lập (không chồng lặp)
Backtracking	Cần liệt kê tất cả nghiệm, không gian tìm kiếm nhỏ

Child pages

Bình luận

Không có bình luận tại thời điểm này.