Quy Hoạch Động Cơ Bản (Dynamic Programming)

1. Khái niệm & bản chất của phương pháp Quy hoạch động

Quy hoạch động (Dynamic Programming - DP) là phương pháp giải quyết các bài toán tối ưu hóa và đếm tổ hợp bằng cách chia bài toán thành các bài toán con gối nhau (Overlapping Subproblems) và lưu trữ kết quả của các bài toán con đó vào bảng nhớ (memoization table / DP array) để không phải tính lại nhiều lần.

Một bài toán áp dụng được Quy hoạch động khi thỏa mãn 2 nguyên lý:

1. Cấu trúc con tối ưu (Optimal Substructure): Nghiệm tối ưu của bài toán lớn được xây dựng trực tiếp từ nghiệm tối ưu của các bài toán con nhỏ hơn.
2. Các bài toán con gối nhau (Overlapping Subproblems): Cùng một trạng thái con được gọi đi gọi lại nhiều lần trong quá trình đệ quy (ví dụ: cây đệ quy Fibonacci).

2. Các mô hình Quy hoạch động

2.1. Dãy con tăng dài nhất (Longest Increasing Subsequence — LIS)

Cho dãy $A_1, A_2, \dots, A_N$. Tìm độ dài dãy con tăng dài nhất.

• Cách 1: Quy hoạch động $\mathcal{O}(N^2)$
• Định nghĩa: $dp[i]$ là độ dài dãy con tăng dài nhất kết thúc tại phần tử $A[i]$.
• Công thức: $dp[i] = 1 + \max_{j < i, A[j] < A[i]} dp[j]$.
• Cách 2: Tối ưu $\mathcal{O}(N \log N)$ bằng Tìm kiếm nhị phân
• Duy trì mảng tail[k]: giá trị nhỏ nhất của phần tử cuối cùng của dãy con tăng độ dài $k$.
• Mảng tail luôn có tính chất tăng ngặt $\implies$ Dùng lower_bound để tìm vị trí cập nhật trong $\mathcal{O}(\log N)$.

int lis_fast(const vector<int> &a) {
    vector<int> tail;
    for (int x : a) {
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) tail.push_back(x);
        else *it = x;
    }
    return tail.size();
}

2.2. Bài toán Cái túi 0/1 (0/1 Knapsack Problem)

Cho $N$ đồ vật, đồ vật thứ $i$ có trọng lượng $W_i$ và giá trị $V_i$. Cái túi có sức chứa tối đa $M$.

• Công thức DP 2D: $$dp[i][w] = \max(dp[i-1][w], dp[i-1][w - W_i] + V_i) \quad (\text{với } w \ge W_i)$$

• Tối ưu không gian xuống mảng 1D $\mathcal{O}(M)$: Duyệt trọng lượng $w$ ngược chiều từ $M$ về $W_i$ để đảm bảo mỗi đồ vật chỉ được chọn tối đa 1 lần:

vector<long long> dp(m + 1, 0);
for (int i = 0; i < n; ++i) {
    for (int w = m; w >= weight[i]; --w) {
        dp[w] = max(dp[w], dp[w - weight[i]] + val[i]);
    }
}

3. Mẫu cài đặt chuẩn thi đấu: Xâu con chung dài nhất (LCS)

Cho hai xâu $S$ độ dài $N$ và $T$ độ dài $M$. Tìm độ dài xâu con chung dài nhất.

• Công thức: $$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{khi } S[i-1] == T[j-1] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{khi } S[i-1] \ne T[j-1] \end{cases}$$

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    if (!(cin >> s >> t)) return 0;

    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] << "\n";
    return 0;
}

4. Ranh giới áp dụng