Quy hoạch động (DP)

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ó

1. 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.
2. 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

1. Xác định trạng thái — dp[i] có nghĩa là gì?
2. Xác định công thức chuyển — dp[i] tính từ dp[j] nào?
3. Xác định base case — giá trị khởi tạo.
4. Xác định thứ tự tính — tính dp[i] trước dp[j] hay sau?
5. 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 $\le 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

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

Bài tập luyện

Đề VOI

• Siêu thị may mắn (voi07_market) (Nâng cao) VOI 2007: cái túi đếm số cách với số lượng mỗi loại bị giới hạn; lưu ý đáp số vượt 64 bit.
• Lò cò (voi08_jump) (Trung cấp) VOI 2008: mũi tên luôn đi tới số lớn hơn nên đây là đường đi dài nhất trên DAG, quy hoạch động theo giá trị tăng dần (xem thêm DP trên đồ thị).
• Trò chơi với băng số (voi09_lgame) (Trung cấp) VOI 2009: DP hai trạng thái theo tính chẵn lẻ của số ô đã chọn (cũng có công thức tham lam tương đương).
• Dãy con chung không liền kề dài nhất (voi10_lnacs) (Trung cấp) VOI 2010: biến thể của LCS ở Ví dụ 3, chỉ cần sửa một ô trong công thức chuyển khi ghép hai phần tử bằng nhau.
• Trộn xâu (voi13_merge) (Nâng cao) VOI 2013: DP trên lưới $(i,j)$ như LCS, nhưng phải thêm chiều "ký tự cuối lấy từ xâu nào".
• Dãy con chung bội hai dài nhất (voi14_lcs2x) (Nâng cao) VOI 2014: một biến thể của dãy con chung tăng dài nhất (LCIS) với điều kiện $2c_i\le c_{i+1}$.