Quy hoạch động (Dynamic Programming) toàn tập: Từ trực giác đến cài đặt thuật toán

03/11/2026

Trong tất cả các chuyên đề thuật toán của kỳ thi Tin học trẻ Bảng B, Quy hoạch động (Dynamic Programming - DP) là chủ đề chiếm tỷ trọng điểm số cao nhất và cũng là bài toán quyết định tấm huy chương Vàng, Bạc của thí sinh. Nhiều bạn nghe thấy từ "Quy hoạch động" thường cảm thấy áp lực và sợ hãi. Nhưng bản chất cốt lõi của nó lại xuất phát từ một câu chuyện đố vui rất bình dị:

- Thầy giáo viết lên bảng: 1 + 1 + 1 + 1 + 1 = ?
- Học sinh: "Thưa thầy bằng 5 ạ!"
- Thầy giáo viết thêm "+ 1" vào cuối: 1 + 1 + 1 + 1 + 1 + 1 = ?
- Học sinh trả lời ngay tức khắc: "Bằng 6 ạ!"
- Thầy mỉm cười hỏi: "Tại sao em tính nhanh thế mà không cần đếm lại từ đầu?"
- Học sinh: "Vì em nhớ đoạn trước là 5 rồi, em chỉ cần lấy 5 cộng thêm 1 thôi ạ!"

Đó chính là Quy hoạch động: Lưu lại đáp án của bài toán con đã giải để xây dựng đáp án cho bài toán lớn hơn, tuyệt đối không tính toán trùng lặp!

1. Bốn bước chuẩn mực để chinh phục mọi bài toán DP

Khi gặp một bài toán Quy hoạch động, đừng vội gõ code. Hãy cầm bút chì và giải quyết tuần tự 4 bước trên giấy:

Bước 1 - Định nghĩa trạng thái (State): Mảng dp[i] (hoặc dp[i][j]) có ý nghĩa thực tế là gì? (Ví dụ: dp[i] là số cách đi đến bậc thang thứ i).
Bước 2 - Tìm công thức truy hồi (Transition): Để tính được dp[i], ta có thể suy ra từ những trạng thái nhỏ hơn nào trước đó? (Ví dụ: dp[i] = dp[i-1] + dp[i-2]).
Bước 3 - Xác định giá trị cơ sở (Base Case): Những bài toán con nhỏ nhất có kết quả hiển nhiên bằng bao nhiêu? (Ví dụ: dp[1] = 1, dp[2] = 2).
Bước 4 - Xác định thứ tự tính toán: Cần tính từ giá trị nhỏ đến lớn (Bottom-up) hay tính từ lớn về nhỏ để đảm bảo khi cần giá trị nào thì giá trị đó đã được tính sẵn?

2. Bài toán kinh điển 1: Dãy con tăng dài nhất (LIS - Longest Increasing Subsequence)

Đề bài: Cho dãy gồm N số nguyên a[1], a[2], ..., a[N] (N \le 5000). Hãy tìm độ dài của dãy con tăng dài nhất (các phần tử được chọn không nhất thiết phải đứng liền kề nhau nhưng phải giữ nguyên thứ tự xuất hiện ban đầu).

Phân tích theo 4 bước:

Trạng thái: Gọi dp[i] là độ dài của dãy con tăng dài nhất kết thúc tại phần tử a[i].
Cơ sở: Ban đầu mỗi phần tử đứng một mình tạo thành dãy con độ dài 1 → dp[i] = 1 với mọi i.
Truy hồi: Để tính dp[i], ta xét tất cả các phần tử a[j] đứng trước nó (j < i). Nếu a[j] < a[i] thì ta có thể ghép a[i] vào sau dãy con kết thúc tại a[j]:
dp[i] = \max(dp[i], dp[j] + 1) với mọi j < i thỏa mãn a[j] < a[i].
Đáp án cuối cùng: Là giá trị lớn nhất trong toàn bộ mảng dp.

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    vector<int> dp(n, 1);
    int ans = 1;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    
    cout << ans << "\n";
    return 0;
}

Độ phức tạp: 2 vòng lặp for lồng nhau chạy mất O(N^2). Với N = 5000, số phép tính xấp xỉ 1.25 \times 10^7, chạy chỉ mất 0.05 giây!

3. Bài toán kinh điển 2: Cái túi 0-1 (0-1 Knapsack)

Đề bài: Có N món đồ (N \le 1000). Món thứ i có trọng lượng w[i] và giá trị v[i]. Bạn có một chiếc túi chịu được tải trọng tối đa là W (W \le 10000). Hãy chọn các món đồ bỏ vào túi sao cho tổng giá trị là lớn nhất mà không làm rách túi (mỗi món chỉ được chọn 1 lần hoặc không chọn).

Công thức truy hồi 2 chiều:

Gọi dp[i][j] là giá trị lớn nhất khi xét đến món đồ thứ i và tải trọng túi hiện tại là j:

Không chọn món thứ i: dp[i][j] = dp[i-1][j]
Có chọn món thứ i (nếu j ≥ w[i]): dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

Kỹ thuật tối ưu bộ nhớ đỉnh cao: Nén về mảng 1 chiều

Nhận thấy trạng thái ở dòng i chỉ phụ thuộc duy nhất vào dòng i - 1 ngay trước nó. Ta có thể dùng duy nhất một mảng 1 chiều dp[j] nếu cho biến tải trọng j duyệt ngược từ W về w[i]:

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

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    
    vector<long long> dp(W + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        // DUYỆT NGƯỢC TỪ W VỀ w[i] để tránh việc dùng 1 món đồ nhiều lần!
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    cout << dp[W] << "\n";
    return 0;
}

Bí mật sống còn: Tại sao phải duyệt ngược từ W xuống w[i]? Vì nếu bạn duyệt xuôi từ w[i] lên W, trạng thái dp[j] sẽ dùng giá trị dp[j - w[i]] vừa mới cập nhật ở cùng lượt i đó, đồng nghĩa với việc bạn được chọn món đồ thứ i nhiều lần (đây là bài toán Knapsack không giới hạn số lượng)!

Lời khuyên luyện tập

Quy hoạch động giống như việc học bơi: không thể giỏi bằng cách chỉ đọc lý thuyết. Bạn bắt buộc phải thực hành vẽ bảng trên giấy và nộp code. Hãy bắt đầu ngay với bộ bài tập Quy hoạch động cơ bản tại mục Luyện đề & Thuật toán trên BitCode.vn!

#C++#Tin học trẻ #Thuật toán #Quy hoạch động