I. Giới thiệu về Quy hoạch động
Trong lĩnh vực lập trình và thuật toán, Quy hoạch động là một kỹ thuật mạnh mẽ được sử dụng để giải quyết các bài toán có tính chất đệ quy với các bài toán con trùng lặp. Khi cài đặt các bài toán quy hoạch động, chúng ta thường sử dụng hai phương pháp chính: Top-down và Bottom-up.
1. Phương pháp Bottom-up (Từ dưới lên)
Cách tiếp cận này khởi đầu từ những bài toán nhỏ và dần dần tính toán để giải quyết các bài toán lớn hơn dựa trên công thức truy hồi. Phương pháp này thường được thực hiện bằng cách sử dụng kỹ thuật tabulation (điền bảng phương án). Lợi ích của cách tiếp cận này là nhanh chóng và hiệu quả nhưng yêu cầu nhiều thời gian cài đặt.
2. Phương pháp Top-down (Từ trên xuống)
Ngược lại với phương pháp Bottom-up, phương pháp Top-down sử dụng đệ quy để phân tách bài toán lớn thành các bài toán nhỏ hơn. Kỹ thuật đệ quy có nhớ (memoization) được áp dụng để tránh tính toán lặp lại các bài toán đã có kết quả. Phương pháp này dễ cài đặt hơn nhưng tốn nhiều bộ nhớ.
3. So sánh giữa Top-down và Bottom-up
Dưới đây là bảng so sánh chi tiết giữa hai phương pháp:
| Phương pháp Top-down | Phương pháp Bottom-up |
|---|---|
| Sử dụng đệ quy có nhớ | Sử dụng kỹ thuật điền bảng liên tục |
| Dễ cài đặt nhưng thường chậm hơn do gọi đệ quy | Cài đặt phức tạp nhưng có tốc độ chạy cao hơn |
| Khó khăn trong việc áp dụng các kỹ thuật cải tiến | Dễ dàng áp dụng các kỹ thuật cải tiến |
II. Ví dụ minh họa
1. Dãy Fibonacci
Đề bài
Cho số nguyên dương n, hãy tìm số Fibonacci thứ n. Định nghĩa Dãy Fibonacci như sau:
f0 = 0, f1 = 1, fi = fi−1 + fi−2 (∀ i > 1)
Cài đặt Top-down
cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int fibo(int n, vector<int> &f) {
if (n <= 1) return n;
if (f[n] != 0) return f[n];
f[n] = (fibo(n - 1, f) + fibo(n - 2, f)) % mod;
return f[n];
}
int main() {
int n;
cin >> n;
vector<int> f(n + 1);
cout << fibo(n, f);
}Cài đặt Bottom-up
cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int main() {
int n;
cin >> n;
vector<int> f(n + 1);
f[0] = 0; f[1] = 1;
for (int i = 2; i <= n; ++i)
f[i] = (f[i - 1] + f[i - 2]) % mod;
cout << f[n];
}III. Kết luận
Tùy vào từng bài toán cụ thể mà bạn có thể lựa chọn giữa phương pháp Top-down và Bottom-up trong quy hoạch động. Hai phương pháp này đều có ưu điểm và hạn chế riêng, và việc nắm rõ chúng sẽ giúp bạn giải quyết các bài toán tối ưu một cách hiệu quả hơn.
