[DP] QUY HOẠCH ĐỘNG cơ bản

by admin | Apr 28, 2025 | Cấu trúc dữ liệu và giải thuật, Quy hoạch động | 0 comments

Mục tiêu

Hiểu khái niệm cơ bản của Quy hoạch Động (Dynamic Programming – DP).
Nắm được cách áp dụng DP để giải các bài toán tối ưu.
Thực hành giải một bài toán DP cơ bản.

1. Quy hoạch Động là gì?

Quy hoạch động (Dynamic Programming – QHĐ) là một kỹ thuật giải bài toán hiệu quả bằng cách chia bài toán lớn thành các bài toán con nhỏ hơn, kết quả của các bài toán con đã giải được lưu lại để giải cho các bài toán lớn hơn sau đó mà không cần phải tính toán lại. DP thường được áp dụng khi bài toán có các đặc điểm sau:

Bài toán con gối nhau (Overlapping Subproblems): Các bài toán con cùng tính chất lặp lại nhiều lần.
Cấu trúc tối ưu (Optimal Substructure): Lời giải của bài toán lớn có thể được xây dựng từ lời giải của các bài toán con.

Ví dụ: Tính số Fibonacci thứ n có thể dùng DP vì Fib(n) = Fib(n-1) + Fib(n-2), và các giá trị Fib(n-1), Fib(n-2) được tính lặp lại. Hình minh họa dưới cho trường hợp tính Fib(5)

Trong quy hoạch động, ta phải xác định được các yếu tố sau:

Xác định trạng thái: biểu diễn bài toán con bằng một biến hoặc tổ hợp các biến.
Xây dựng công thức truy hồi: cách tính bài toán lớn từ các bài toán nhỏ hơn.
Khởi tạo giá trị ban đầu (base case).
Tính kết quả các bài toán con theo thứ tự tăng dần để đảm bảo khi cần dùng kết quả của bài toán nhỏ hơn, nó đã được tính rồi.

Dựa trên kỹ thuật lưu trữ kết quả trung gian, Phương pháp Quy hoạch động cho kết quả nhanh hơn các phương pháp như quay lui (backtracking) hay duyệt toàn bộ (brute-force), thường chỉ có độ phức tạp đa thức, giúp giải được những bài toán với kích thước dữ liệu lớn.

2. Các bước giải bài toán bằng Quy hoạch Động

Xác định trạng thái (State): Xác định biến hoặc tập hợp các biến đại diện cho bài toán con.
Ví dụ: Trong bài toán Fibonacci, trạng thái là dp[i] tương ứng là số Fibonacci thứ i.
Xây dựng công thức truy hồi (Recurrence Relation): Viết công thức tính trạng thái dựa trên các trạng thái nhỏ hơn.
Ví dụ: dp[i] = dp[i-1] + dp[i-2].
Khởi tạo giá trị ban đầu (Base Case): Xác định các trạng thái cơ bản. Ví dụ: dp[0] = 0, dp[1] = 1.
Tính toán và lưu kết quả: Dùng vòng lặp hoặc đệ quy với lưu trữ (memoization) để tính các trạng thái.
Trả lời bài toán: Dựa trên trạng thái cuối cùng hoặc kết hợp các trạng thái để đưa ra đáp án.

3. Ví dụ minh họa: Dãy con tăng dài nhất (Longest Increasing Subsequence – LIS)

Bài toán

Cho một dãy số A gồm n phần tử. Tìm độ dài của dãy con tăng dài nhất.

Dãy con của một dãy số là một dãy được tạo ra bằng cách xóa đi một số phần tử (có thể là không liên tiếp) trong dãy ban đầu mà không làm thay đổi thứ tự tương đối giữa các phần tử còn lại.

Ví dụ:

Input: A = [10, 22, 9, 33, 21, 50, 41, 60]
Output: 5 (Dãy con tăng dài nhất là [10, 22, 33, 50, 60])

Phân tích theo hướng DP

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 chỉ số i.
Công thức truy hồi:
- Với mỗi i, kiểm tra tất cả j < i sao cho A[j] < A[i].
- dp[i] = max(dp[j]) + 1 với mọi j thỏa mãn điều kiện.
Khởi tạo: dp[i] = 1 (xem mỗi phần tử tự nó là một dãy con tăng độ dài 1 – chỉ có chính nó).
Kết quả: max(dp[i]) với mọi i.

Mã nguồn tham khảo

#include <iostream>
#include <vector>
#include <algorithm>  // dùng cho hàm max

using namespace std;

int longest_increasing_subsequence(const vector<int>& A) {
    int n = A.size();
    vector<int> dp(n, 1);  // Khởi tạo dp[i] = 1
    int res = 1;  // Biến lưu độ dài lớn nhất

    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);
            }
        }
        res = max(res, dp[i]);  // Cập nhật kết quả tại mỗi bước
    }

    return res;
}

int main() {
    vector<int> A = {10, 22, 9, 33, 21, 50, 41, 60};
    cout << longest_increasing_subsequence(A) << endl;  // Output: 5
    return 0;
}

4. Các dạng bài toán DP phổ biến

DP trên dãy: Ví dụ: Dãy con tăng dài nhất, tổng lớn nhất của dãy con.
DP trên lưới: Ví dụ: Tìm đường đi có tổng tối thiểu trên ma trận.
DP với trạng thái phức tạp: Ví dụ: Bài toán cái túi (Knapsack), lập lịch.

5. Bài tập thực hành

Bài toán: Leo cầu thang

Có một cầu thang với n bậc. Mỗi bước, bạn có thể leo 1 hoặc 2 bậc. Hỏi có bao nhiêu cách để leo đến bậc thứ n?

Input: n = 3
Output: 3 (Các cách: [1,1,1], [1,2], [2,1])

Yêu cầu:

Viết chương trình sử dụng DP để giải bài toán.
Gợi ý:
- Trạng thái: dp[i] là số cách để leo đến bậc thứ i.
- Công thức: dp[i] = dp[i-1] + dp[i-2].
- Khởi tạo: dp[0] = 1, dp[1] = 1.

Mã nguồn tham khảo

#include <iostream>
#include <vector>

using namespace std;

int climb_stairs(int n) {
    if (n <= 1) {
        return 1;
    }

    vector<int> dp(n + 1, 0);  // Khởi tạo mảng dp kích thước n+1
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    cout << climb_stairs(3) << endl;  // Output: 3
    return 0;
}

6. Kết luận

Quy hoạch Động là công cụ mạnh mẽ để giải các bài toán tối ưu.
Để thành thạo DP, cần luyện tập nhận diện trạng thái và xây dựng công thức truy hồi.
Thực hành nhiều bài toán DP cơ bản để làm quen với tư duy.

Tài liệu tham khảo

Bài viết gốc: VNOI Wiki – Quy hoạch Động
Các nguồn học DP: Codeforces, LeetCode, TopCoder.