Quy hoạch động (1)
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 90 phút
- Học trước
- Hàm tự tạo và đệ quy
- Chủ đề
- quy hoạch động
- Trạng thái
Kiến thức cơ bản
Vì sao cần quy hoạch động
Gấu Po muốn tính số Fibonacci F(n): F(1) = 1, F(2) = 1 và F(n) = F(n-1) + F(n-2). Ở tuần 7, em đã viết hàm đệ quy cho dãy này. Hãy xem Gấu Po phải làm gì khi tính F(5):
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)
/ \
F(2) F(1)
F(3) bị tính 2 lần, F(2) bị tính 3 lần, dù kết quả của chúng lúc nào cũng giống nhau. Khi n lớn, hàm đệ quy cứ gọi lại các bài toán cũ rất nhiều lần: tính F(30) mất hơn 1,6 triệu lần gọi hàm, tính F(40) mất hơn 200 triệu lần gọi hàm. Số phép tính tăng gần gấp đôi mỗi khi n tăng thêm 1, cỡ O(2n), chậm hơn quy ước 108 rất nhiều.
Gấu Po nghĩ ra một cách: "Mỗi bài toán con chỉ giải một lần, ghi kết quả vào cuốn sổ tay. Lần sau cần thì giở sổ ra xem, không tính lại nữa." Cách làm đó gọi là quy hoạch động (Dynamic Programming, viết tắt là DP). Cuốn sổ tay chính là một mảng dp. Với n = 106, chỉ cần khoảng 106 phép tính, nhanh trong một cái chớp mắt.
Các đoạn code dưới đây là phần thân hàm main (đã có #include <bits/stdc++.h> và using namespace std;).
Ba bước làm một bài DP
- Bước 1: Đặt tên cho bài toán con. Viết bằng một câu tiếng Việt xem dp[i] nghĩa là gì. Ví dụ: dp[i] = số cách leo từ mặt đất lên bậc thứ i.
- Bước 2: Tìm công thức truy hồi. dp[i] được tính từ những ô nhỏ hơn nào? Hãy tự hỏi: "Bước cuối cùng của mình là gì?" Mỗi lựa chọn cho bước cuối sẽ dẫn về một bài toán con nhỏ hơn.
- Bước 3: Chọn trường hợp cơ sở và thứ tự tính. Những ô nhỏ nhất (như dp[0], dp[1]) không dùng được công thức, em phải tự điền sẵn. Sau đó tính i từ nhỏ đến lớn; đáp án thường nằm ở dp[n].
Ví dụ 1: Fibonacci
Bước 1: dp[i] = F(i), tức là số Fibonacci thứ i. Bước 2: dp[i] = dp[i-1] + dp[i-2]. Bước 3: dp[1] = dp[2] = 1, rồi tính i = 3, 4, ..., n. Đáp án là dp[n].
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
dp[i] | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21
Ví dụ: dp[5] = dp[4] + dp[3] = 3 + 2 = 5
Cách 1: Tính từ nhỏ đến lớn (bảng dp)
int n;
cin >> n;
vector<long long> dp(n + 2); // dp[i] = F(i); dư 1 ô cho n = 1
dp[1] = dp[2] = 1; // trường hợp cơ sở
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // công thức truy hồi
}
cout << dp[n] << endl;
Cách 2: Đệ quy có nhớ (memoization)
Giữ nguyên hàm đệ quy cũ, chỉ thêm "cuốn sổ": trước khi tính thì nhìn sổ, tính xong thì ghi vào sổ. Em đặt mảng memo và hàm fib ở ngoài hàm main.
vector<long long> memo(100, -1); // -1 nghĩa là chưa tính
long long fib(int i) {
if (i <= 2) return 1; // trường hợp cơ sở
if (memo[i] != -1) return memo[i]; // đã có trong sổ: lấy luôn
memo[i] = fib(i - 1) + fib(i - 2); // chưa có: tính rồi ghi sổ
return memo[i];
}
Mỗi giá trị i chỉ được tính đúng một lần nên cả hai cách đều chạy trong O(n). Cách 1 ngắn gọn và hay dùng nhất. Cách 2 tự nhiên với bạn đã quen đệ quy, nhưng nếu n quá lớn (cỡ 106) thì đệ quy quá sâu có thể bị tràn bộ nhớ.
Ví dụ 2: Leo cầu thang
Gấu Po leo cầu thang n bậc, xuất phát từ mặt đất (bậc 0). Mỗi bước, Gấu Po leo 1 hoặc 2 bậc. Hỏi có bao nhiêu cách leo lên bậc thứ n? Với n = 3 có 3 cách: (1, 1, 1), (1, 2), (2, 1).
- Bước 1: dp[i] = số cách leo từ mặt đất lên bậc i.
- Bước 2: Bước cuối cùng để đứng ở bậc i chỉ có hai khả năng: từ bậc i-1 bước lên 1 bậc, hoặc từ bậc i-2 bước lên 2 bậc. Hai nhóm cách này khác hẳn nhau nên ta cộng lại: dp[i] = dp[i-1] + dp[i-2].
- Bước 3: dp[0] = 1 (đứng yên ở mặt đất là 1 cách "chưa cần làm gì"), dp[1] = 1. Đáp án là dp[n].
bậc i | 0 | 1 | 2 | 3 | 4 | 5
dp[i] | 1 | 1 | 2 | 3 | 5 | 8
dp[5] = dp[4] + dp[3] = 5 + 3 = 8
(bước cuối 1 bậc) (bước cuối 2 bậc)
const long long MOD = 1000000007; // đặt ngoài hàm main
int n;
cin >> n;
vector<long long> dp(n + 2);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD; // lấy dư ngay
}
cout << dp[n] << endl;
Số cách tăng rất nhanh: với n = 100 đã vượt khỏi long long. Vì vậy các đề DP đếm số cách thường yêu cầu "in kết quả chia dư cho 109 + 7". Em lấy dư sau mỗi phép cộng, và dùng long long để không bị tràn số.
Đếm, nhỏ nhất, lớn nhất: chỉ đổi dòng công thức
Cùng một cách chia bài toán con, nhưng tùy đề hỏi gì mà ta gom các lựa chọn của bước cuối theo cách khác nhau:
| Đề hỏi | Gom các lựa chọn bằng | Ví dụ |
|---|---|---|
| Có bao nhiêu cách | Cộng: dp[i] = tổng các dp[j] của mọi ô j mà từ đó bước tới i được | Leo cầu thang 1 hoặc 2 bậc |
| Ít nhất (chi phí nhỏ nhất) | min: dp[i] = min của (dp[j] + chi phí của bước j → i) | Leo thang tốn ít sức nhất |
| Nhiều nhất (giá trị lớn nhất) | max: dp[i] = max của (dp[j] + giá trị của bước j → i) | Nhặt được nhiều điểm nhất |
Khi tìm nhỏ nhất, những ô chưa biết cách nào đến được nên được điền một số rất lớn (gọi là INF) để lệnh min không chọn nhầm các ô đó.
DP khác tham lam ở đâu
Ở hai tuần trước, tham lam luôn chọn ngay lựa chọn có vẻ tốt nhất lúc này. Có bài làm vậy lại sai. Hổ cần trả đúng 10 đồng bằng các tờ tiền mệnh giá 1, 5 và 6. Tham lam lấy tờ to nhất trước: 6 + 1 + 1 + 1 + 1 là 5 tờ. Nhưng 5 + 5 chỉ cần 2 tờ! DP không đoán, mà thử mọi khả năng của bước cuối rồi chọn cái tốt nhất; nhờ cuốn sổ tay nên cách này vẫn rất nhanh.
Nhận dạng đề bài
| Dấu hiệu trong đề | Nên nghĩ tới |
|---|---|
| "Có bao nhiêu cách", kèm "chia dư cho 109 + 7" | DP đếm: cộng các nhóm cách khác nhau |
| "Ít nhất", "nhiều nhất" mà thử tham lam với số nhỏ thì sai | DP min hoặc max |
| Đáp án cho n suy ra được từ đáp án cho n-1, n-2, ... | Đặt dp[i], viết công thức truy hồi |
| n lớn (105, 106) nên không thể thử hết mọi cách | Cần cách O(n) hoặc O(n log n), nghĩ tới DP |
Mở rộng (không bắt buộc): chỉ nhớ hai ô gần nhất
Fibonacci chỉ cần hai ô liền trước nên không cần cả mảng, ta thay bằng hai biến:
long long fPrev = 1, fCur = 1; // F(1) và F(2)
for (int i = 3; i <= n; i++) {
long long fNext = fPrev + fCur;
fPrev = fCur; // dời lên một ô
fCur = fNext;
}
cout << fCur << endl;
Luyện tập
Bài 1. Dãy số của Thỏ
Thỏ viết một dãy số: hai số đầu đều là 1, từ số thứ ba trở đi, mỗi số bằng tổng của hai số đứng ngay trước nó: 1, 1, 2, 3, 5, 8, ... Hãy giúp Thỏ tìm số thứ n của dãy.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 90). | |
|---|---|---|
| Đầu ra | Số thứ n của dãy (vẫn nằm trong kiểu long long). | |
| Test | Input | Output |
| 1 | 10 | 55 |
| 2 | 90 | 2880067194370816120 |
Bài 2. Gấu Po leo cầu thang
Cầu thang nhà Thỏ có n bậc. Mỗi bước, Gấu Po leo 1 hoặc 2 bậc. Hỏi Gấu Po có bao nhiêu cách leo từ mặt đất lên bậc thứ n? Hai cách leo khác nhau nếu có ít nhất một bước khác nhau. Vì số cách rất lớn, hãy in kết quả sau khi chia dư cho 109 + 7.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 106). | |
|---|---|---|
| Đầu ra | Số cách leo, chia dư cho 109 + 7. | |
| Test | Input | Output |
| 1 | 4 | 5 |
| 2 | 10 | 89 |
Bài 3. Cầu thang của Hổ
Hổ chân dài hơn Gấu Po: mỗi bước Hổ leo được 1, 2 hoặc 3 bậc. Cầu thang có n bậc. Hỏi Hổ có bao nhiêu cách leo từ mặt đất lên bậc thứ n? In kết quả chia dư cho 109 + 7.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 106). | |
|---|---|---|
| Đầu ra | Số cách leo, chia dư cho 109 + 7. | |
| Test | Input | Output |
| 1 | 4 | 7 |
| 2 | 10 | 274 |
Bài 4. Leo thang tốn sức
Thỏ leo cầu thang n bậc, mỗi bước leo 1 hoặc 2 bậc. Đứng ở mặt đất (bậc 0) không tốn sức. Mỗi lần đặt chân lên bậc i, Thỏ tốn c[i] năng lượng (kể cả bậc cuối cùng, bậc bị bước qua thì không tốn). Hỏi Thỏ cần ít nhất bao nhiêu năng lượng để lên đến bậc n?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên c[i] (1 ≤ c[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng năng lượng ít nhất. | |
| Test | Input | Output |
| 1 | 5 3 2 4 1 5 | 8 |
| 2 | 3 6 7 1 | 7 |
Bài 5. Thỏ nhảy đá
Dòng suối có n hòn đá xếp thành hàng, đánh số từ 1 đến n; hòn đá thứ i có độ cao h[i]. Thỏ đứng ở hòn đá 1 và muốn sang hòn đá n. Từ hòn đá i, Thỏ nhảy được sang hòn đá i+1 hoặc i+2. Cú nhảy từ hòn đá i sang hòn đá j tốn sức |h[i] - h[j]|. Tính tổng sức nhỏ nhất để Thỏ đến hòn đá n.
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 105). Dòng 2: n số nguyên h[i] (1 ≤ h[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng sức nhỏ nhất. | |
| Test | Input | Output |
| 1 | 4 10 30 40 20 | 30 |
| 2 | 5 50 10 20 90 40 | 50 |
Bài 6. Thỏ nhảy xa
Thỏ tập luyện nên nhảy xa hơn: từ hòn đá i, Thỏ nhảy được sang một trong các hòn đá i+1, i+2, ..., i+k (không vượt quá hòn đá n). Cú nhảy từ hòn đá i sang hòn đá j vẫn tốn sức |h[i] - h[j]|. Tính tổng sức nhỏ nhất để Thỏ đi từ hòn đá 1 đến hòn đá n. Gợi ý: với n = 105 và k = 100, em cần khoảng n × k = 107 phép tính, vẫn rất nhanh.
| Đầu vào | Dòng 1: hai số nguyên n, k (2 ≤ n ≤ 105; 1 ≤ k ≤ 100). Dòng 2: n số nguyên h[i] (1 ≤ h[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng sức nhỏ nhất. | |
| Test | Input | Output |
| 1 | 5 3 10 30 40 50 20 | 30 |
| 2 | 6 2 30 10 60 10 60 50 | 40 |
Bài 7. Cầu thang hỏng
Cầu thang nhà Gấu Po có n bậc, trong đó m bậc bị hỏng nên Gấu Po không được đặt chân lên. Mỗi bước Gấu Po leo 1 hoặc 2 bậc (được phép bước qua bậc hỏng). Hỏi có bao nhiêu cách leo từ mặt đất lên bậc thứ n? In kết quả chia dư cho 109 + 7. Nếu bậc n bị hỏng thì không có cách nào.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ m ≤ n ≤ 106). Dòng 2: m số nguyên khác nhau b[i] (1 ≤ b[i] ≤ n) là các bậc bị hỏng. | |
|---|---|---|
| Đầu ra | Số cách leo, chia dư cho 109 + 7. | |
| Test | Input | Output |
| 1 | 6 1 3 | 4 |
| 2 | 5 2 2 4 | 1 |
Bài 8. Đổi tiền ít tờ nhất
Hổ cần trả đúng S đồng. Hổ có k loại tờ tiền, mỗi loại có rất nhiều tờ. Hỏi Hổ cần dùng ít nhất bao nhiêu tờ để trả đúng S đồng? Nếu không thể trả đúng thì in -1. Cẩn thận: cách tham lam (luôn lấy tờ to nhất) có thể cho kết quả sai.
| Đầu vào | Dòng 1: hai số nguyên k, S (1 ≤ k ≤ 100; 1 ≤ S ≤ 105). Dòng 2: k mệnh giá khác nhau (1 ≤ mệnh giá ≤ 105). | |
|---|---|---|
| Đầu ra | Số tờ ít nhất, hoặc -1 nếu không thể trả đúng S đồng. | |
| Test | Input | Output |
| 1 | 3 6 1 3 4 | 2 |
| 2 | 2 7 2 4 | -1 |
Bài 9. Lát nền nhà Thỏ
Nền nhà Thỏ là hình chữ nhật gồm 2 hàng, n cột (2 × n ô vuông). Thỏ có rất nhiều viên gạch 1 × 2 ô, được phép đặt nằm ngang hoặc dựng đứng. Có bao nhiêu cách lát kín nền nhà, không hở và không chồng lên nhau? In kết quả chia dư cho 109 + 7. Gợi ý: nhìn vào cột đầu tiên, viên gạch phủ ô trên cùng bên trái có thể đặt theo mấy kiểu?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 106). | |
|---|---|---|
| Đầu ra | Số cách lát, chia dư cho 109 + 7. | |
| Test | Input | Output |
| 1 | 1 | 1 |
| 2 | 4 | 5 |
Bài tập tự luyện
Bài 1. Dãy số của Gấu Po
Gấu Po tạo một dãy số a: a[1] = 1, a[2] = 2, từ số thứ ba trở đi, a[i] = 2 × a[i-1] + a[i-2]. Hãy tìm a[n]. In kết quả chia dư cho 109 + 7.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 106). | |
|---|---|---|
| Đầu ra | Giá trị a[n], chia dư cho 109 + 7. | |
| Test | Input | Output |
| 1 | 5 | 29 |
| 2 | 1 | 1 |
Bài 2. Dãy đèn lồng
Phố đèn lồng có n chiếc đèn xếp thành một hàng, mỗi chiếc hoặc sáng hoặc tắt. Để tiết kiệm điện, không được có hai chiếc đèn sáng đứng cạnh nhau. Có bao nhiêu cách bật tắt cả hàng đèn? In kết quả chia dư cho 109 + 7.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 106). | |
|---|---|---|
| Đầu ra | Số cách, chia dư cho 109 + 7. | |
| Test | Input | Output |
| 1 | 3 | 5 |
| 2 | 4 | 8 |
Bài 3. Bước chân tùy chọn
Hổ chỉ bước được những bước có độ dài thuộc một danh sách cho trước d[1], d[2], ..., d[k] (đơn vị: bậc). Cầu thang có n bậc. Hỏi Hổ có bao nhiêu cách leo từ mặt đất lên đúng bậc thứ n? Hai cách khác nhau nếu thứ tự các bước khác nhau. In kết quả chia dư cho 109 + 7.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 105; 1 ≤ k ≤ 10). Dòng 2: k số nguyên khác nhau d[j] (1 ≤ d[j] ≤ n). | |
|---|---|---|
| Đầu ra | Số cách leo, chia dư cho 109 + 7 (in 0 nếu không có cách nào). | |
| Test | Input | Output |
| 1 | 7 3 1 3 4 | 15 |
| 2 | 5 2 2 4 | 0 |
Bài 4. Hái kẹo ven đường
Con đường có n ngôi nhà, nhà thứ i treo a[i] viên kẹo. Gấu Po không dám lấy kẹo ở hai ngôi nhà liền kề (chủ nhà sẽ phát hiện). Hỏi Gấu Po lấy được nhiều nhất bao nhiêu viên kẹo?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng số kẹo lớn nhất. | |
| Test | Input | Output |
| 1 | 5 2 7 9 3 1 | 12 |
| 2 | 3 10 1 10 | 20 |
Bài 5. Hàng cờ của Thỏ
Thỏ xếp n lá cờ thành một hàng, mỗi lá cờ màu đỏ hoặc màu xanh. Thỏ không thích ba lá cờ liên tiếp cùng một màu. Hỏi Thỏ có bao nhiêu cách xếp? In kết quả chia dư cho 109 + 7.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 106). | |
|---|---|---|
| Đầu ra | Số cách xếp, chia dư cho 109 + 7. | |
| Test | Input | Output |
| 1 | 4 | 10 |
| 2 | 3 | 6 |
Bài 6. Bậc thang có chìa khóa
Gấu Po leo n bậc thang, mỗi bước 1 hoặc 2 bậc. Chiếc chìa khóa nằm ở bậc thứ x nên Gấu Po bắt buộc phải đặt chân lên bậc x (không được bước qua nó). Hỏi có bao nhiêu cách leo từ mặt đất lên bậc n? In kết quả chia dư cho 109 + 7.
| Đầu vào | Dòng 1: hai số nguyên n, x (1 ≤ x ≤ n ≤ 106). | |
|---|---|---|
| Đầu ra | Số cách leo, chia dư cho 109 + 7. | |
| Test | Input | Output |
| 1 | 5 2 | 6 |
| 2 | 7 4 | 15 |
Bài 7. Không bước vọt liên tiếp
Hổ leo n bậc thang, mỗi bước 1 hoặc 2 bậc. Nhưng Hổ mệt nên không bao giờ bước 2 bậc hai lần liên tiếp (bước 2 bậc xong thì bước tiếp phải là 1 bậc). Hỏi Hổ có bao nhiêu cách leo từ mặt đất lên bậc n? In kết quả chia dư cho 109 + 7.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 106). | |
|---|---|---|
| Đầu ra | Số cách leo, chia dư cho 109 + 7. | |
| Test | Input | Output |
| 1 | 4 | 4 |
| 2 | 5 | 6 |
Bài 8. Lát gạch hai loại
Nền nhà gồm 2 hàng, n cột (2 × n ô). Thỏ có hai loại gạch, mỗi loại có rất nhiều viên: gạch 1 × 2 ô (đặt ngang hoặc dựng đứng đều được) và gạch vuông 2 × 2 ô. Có bao nhiêu cách lát kín nền nhà? In kết quả chia dư cho 109 + 7.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 106). | |
|---|---|---|
| Đầu ra | Số cách lát, chia dư cho 109 + 7. | |
| Test | Input | Output |
| 1 | 3 | 5 |
| 2 | 2 | 3 |
Bài 9. Thử thách: Bước chân nguyên tố
Mỗi bước, Thỏ chỉ được leo một số bậc là số nguyên tố (2, 3, 5, 7, 11, ...). Cầu thang có n bậc. Hỏi Thỏ có bao nhiêu cách leo từ mặt đất lên đúng bậc thứ n? Hai cách khác nhau nếu thứ tự các bước khác nhau. In kết quả chia dư cho 109 + 7. Gợi ý: dùng sàng nguyên tố ở tuần 5 để lập danh sách các bước được phép, mỗi ô dp[i] thử hết các bước đó. Với n = 5000 có 669 số nguyên tố nên cần khoảng 5000 × 669, vẫn rất nhanh.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 5000). | |
|---|---|---|
| Đầu ra | Số cách leo, chia dư cho 109 + 7 (in 0 nếu không có cách nào). | |
| Test | Input | Output |
| 1 | 7 | 6 |
| 2 | 3 | 1 |
- Gợi ý chung: Trước khi gõ code, hãy viết ra giấy ba thứ: dp[i] nghĩa là gì, công thức truy hồi, và các ô nhỏ nhất như dp[0], dp[1] bằng bao nhiêu. Tính tay bảng dp với n nhỏ (n = 4 hoặc 5) rồi so với ví dụ của đề. Những lỗi hay gặp: (1) mảng dp thiếu ô, hãy khai báo n + 1 hoặc n + 2 phần tử; (2) dùng dp[i-2] khi i = 1 nên truy cập ra ngoài mảng; (3) bài đếm số cách quên lấy dư hoặc quên dùng long long; (4) bài tìm nhỏ nhất quên điền INF cho ô chưa đến được (nếu điền 0 thì lệnh min luôn chọn nhầm 0).