Khi giải các bài toán quy hoạch động trong sách Thông tin học Olympic, ta cần áp dụng linh hoạt các kỹ thuật như DP số học, DP trạng thái nén, DP trên cây, DP theo khoảng và tối ưu bằng hàng đợi đơn điệu. Dưới đây là phân tích và mã nguồn minh họa cho từng dạng.

DP Số học (Digit DP)

Đây là kỹ thuật đếm số thỏa mãn điều kiện dựa trên từng chữ số. Ta thường dùng mảng dp[len][digit] để lưu số lượng số có độ dài len và bắt đầu bằng digit.

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

ll comb(int n, int k) {
    if (k > n || k < 0) return 0;
    ll res = 1;
    for (int i = 0; i < k; ++i) {
        res = res * (n - i) / (i + 1);
    }
    return res;
}

ll countValid(ll x, int base, int targetOnes) {
    vector<int> digits;
    while (x) {
        digits.push_back(x % base);
        x /= base;
    }
    reverse(digits.begin(), digits.end());
    
    int len = digits.size();
    ll total = 0;
    int remaining = targetOnes;
    
    for (int i = 0; i < len; ++i) {
        if (digits[i] > 1) {
            for (int j = i; j < len; ++j) digits[j] = 1;
            break;
        }
        if (digits[i] == 1) {
            total += comb(len - i - 1, remaining);
            --remaining;
            if (remaining < 0) break;
        }
    }
    return total;
}

int main() {
    ll L, R; int K, B;
    cin >> L >> R >> K >> B;
    cout << countValid(R + 1, B, K) - countValid(L, B, K) << endl;
    return 0;
}

DP Trạng thái nén (Bitmask DP)

Dùng khi trạng thái có thể biểu diễn bằng dãy bit. Ví dụ: đặt quân vua trên bàn cờ sao cho không tấn công lẫn nhau.

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

const int MAXN = 12;
ll ways[MAXN][1 << MAXN][MAXN * MAXN];
vector<int> validStates;
int popcount[1 << MAXN];

int main() {
    int N, K;
    cin >> N >> K;
    
    for (int mask = 0; mask < (1 << N); ++mask) {
        if ((mask & (mask << 1)) == 0) {
            validStates.push_back(mask);
            popcount[mask] = __builtin_popcount(mask);
        }
    }
    
    for (int state : validStates) {
        if (popcount[state] <= K) {
            ways[1][state][popcount[state]] = 1;
        }
    }
    
    for (int row = 2; row <= N; ++row) {
        for (int curr : validStates) {
            for (int prev : validStates) {
                if ((curr & prev) || ((curr << 1) & prev) || ((curr >> 1) & prev))
                    continue;
                for (int used = 0; used + popcount[curr] <= K; ++used) {
                    ways[row][curr][used + popcount[curr]] += ways[row-1][prev][used];
                }
            }
        }
    }
    
    ll result = 0;
    for (int row = 1; row <= N; ++row)
        for (int state : validStates)
            result += ways[row][state][K];
            
    cout << result << endl;
    return 0;
}

DP Trên Cây (Tree DP)

Xử lý các bài toán trên cấu trúc cây, thường dùng DFS để duyệt và tính toán từ lá lên gốc.

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

const int MAXN = 1505;
vector<int> adj[MAXN];
int dp[MAXN][2]; // dp[u][0]: không chọn u, dp[u][1]: chọn u

void dfs(int u, int parent) {
    dp[u][1] = 1; // chi phí đặt lính canh tại u
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u);
        dp[u][0] += dp[v][1]; // nếu không chọn u thì phải chọn tất cả con
        dp[u][1] += min(dp[v][0], dp[v][1]); // nếu chọn u thì con có thể chọn hoặc không
    }
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int node, childCount;
        cin >> node >> childCount;
        for (int j = 0; j < childCount; ++j) {
            int child;
            cin >> child;
            adj[node].push_back(child);
            adj[child].push_back(node);
        }
    }
    dfs(0, -1);
    cout << min(dp[0][0], dp[0][1]) << endl;
    return 0;
}

DP Theo Khoảng (Interval DP)

Thường dùng cho các bài toán chia dãy thành đoạn, ví dụ bài hợp nhất đá.

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

const int MAXN = 210;
int sum[MAXN], fMin[MAXN][MAXN], fMax[MAXN][MAXN];

int main() {
    int N;
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> sum[i];
        sum[i + N] = sum[i];
    }
    for (int i = 1; i <= 2 * N; ++i) {
        sum[i] += sum[i - 1];
    }
    
    for (int len = 2; len <= N; ++len) {
        for (int i = 1; i + len - 1 <= 2 * N; ++i) {
            int j = i + len - 1;
            fMin[i][j] = INT_MAX;
            fMax[i][j] = INT_MIN;
            for (int k = i; k < j; ++k) {
                fMin[i][j] = min(fMin[i][j], fMin[i][k] + fMin[k+1][j] + sum[j] - sum[i-1]);
                fMax[i][j] = max(fMax[i][j], fMax[i][k] + fMax[k+1][j] + sum[j] - sum[i-1]);
            }
        }
    }
    
    int ansMin = INT_MAX, ansMax = INT_MIN;
    for (int i = 1; i <= N; ++i) {
        ansMin = min(ansMin, fMin[i][i + N - 1]);
        ansMax = max(ansMax, fMax[i][i + N - 1]);
    }
    cout << ansMin << "\n" << ansMax << endl;
    return 0;
}

Tối ưu bằng Hàng đợi đơn điệu

Dùng để giảm độ phức tạp từ O(n²) xuống O(n) trong một số bài DP có dạng:

dp[i] = min{ dp[j] + cost(j,i) } với j ∈ [i-k, i-1]

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

const int MAXN = 200005;
ll prefix[MAXN], dp[MAXN];
deque<int> dq;

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        cin >> prefix[i];
        prefix[i] += prefix[i - 1];
    }
    
    ll best = LLONG_MIN;
    for (int i = 1; i <= N; ++i) {
        while (!dq.empty() && dq.front() < i - M) dq.pop_front();
        if (!dq.empty()) {
            dp[i] = prefix[i] - prefix[dq.front()];
            best = max(best, dp[i]);
        }
        while (!dq.empty() && prefix[dq.back()] >= prefix[i]) dq.pop_back();
        dq.push_back(i);
    }
    cout << best << endl;
    return 0;
}