Hướng dẫn giải của Cầu thang nhà A Phủ 2
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tính số cách để Bờm leo từ bậc 0 (sân) lên đến bậc N (sàn nhà A Phủ) trên một chiếc cầu thang có N bậc. Bậc thứ N luôn an toàn, nhưng trong số các bậc từ 1 đến N-1 có K bậc bị hỏng (không thể đặt chân lên). Bờm mỗi lần có thể bước lên 1 bậc hoặc 2 bậc. Số lượng cách có thể rất lớn (lên đến 250 chữ số), nên cần sử dụng số lớn (Big Integer).
Các cách tiếp cận
Cách Quy hoạch động cơ bản với số lớn
#include <bits/stdc++.h>
using namespace std;
// Hàm cộng hai số lớn dạng string
string add(string a, string b) {
while (a.size() < b.size()) a = '0' + a;
while (a.size() > b.size()) b = '0' + b;
string res = "";
int carry = 0;
for (int i = a.size() - 1; i >= 0; i--) {
int digit = (a[i] - '0') + (b[i] - '0') + carry;
carry = digit / 10;
digit %= 10;
res = char(digit + '0') + res;
}
if (carry) res = '1' + res;
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<bool> blocked(n + 1, false);
for (int i = 0; i < k; i++) {
int x;
cin >> x;
blocked[x] = true;
}
// dp[i] là số cách để lên được bậc i
vector<string> dp(n + 1, "0");
// Khởi tạo
dp[0] = "1"; // Bắt đầu từ bậc 0
if (!blocked[1]) dp[1] = "1";
for (int i = 2; i <= n; i++) {
if (blocked[i]) continue;
if (!blocked[i-1]) dp[i] = add(dp[i], dp[i-1]);
if (i - 2 >= 0 && !blocked[i-2]) dp[i] = add(dp[i], dp[i-2]);
}
cout << dp[n] << endl;
return 0;
}
- Time Complexity: O(N * L), với L là độ dài của số lớn (tối đa ~250)
- Space Complexity: O(N * L)
Đây là cách tiếp cận trực tiếp dựa trên định nghĩa của quy hoạch động. Ta định nghĩa dp[i] là số cách để lên được bậc thứ i. Công thức truy hồi: dp[i] = dp[i-1] + dp[i-2] nếu bậc i không bị hỏng. Nếu bậc i bị hỏng, dp[i] = 0. Do số cách có thể rất lớn, ta cần tự viết hàm cộng cho các chuỗi ký tự biểu diễn số (Big Integer).
Cách Tối ưu bộ nhớ
#include <bits/stdc++.h>
using namespace std;
string add(string a, string b) {
while (a.size() < b.size()) a = '0' + a;
while (a.size() > b.size()) b = '0' + b;
string res = "";
int carry = 0;
for (int i = a.size() - 1; i >= 0; i--) {
int digit = (a[i] - '0') + (b[i] - '0') + carry;
carry = digit / 10;
digit %= 10;
res = char(digit + '0') + res;
}
if (carry) res = '1' + res;
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<bool> blocked(n + 1, false);
for (int i = 0; i < k; i++) {
int x;
cin >> x;
blocked[x] = true;
}
if (blocked[n]) {
cout << "0" << endl;
return 0;
}
// Chỉ cần lưu 2 giá trị trước đó
string prev2 = "0"; // dp[i-2]
string prev1 = "0"; // dp[i-1]
string current = "0";
// Khởi tạo cho bậc 0 và 1
// dp[0] = 1 luon
prev2 = "1";
if (n >= 1) {
if (blocked[1]) prev1 = "0";
else prev1 = "1";
}
if (n == 0) cout << "1" << endl;
else if (n == 1) cout << prev1 << endl;
else {
for (int i = 2; i <= n; i++) {
if (blocked[i]) {
current = "0";
} else {
current = add(prev1, prev2);
}
// Dịch cửa sổ trượt
prev2 = prev1;
prev1 = current;
}
cout << current << endl;
}
return 0;
}
- Time Complexity: O(N * L)
- Space Complexity: O(L)
Thay vì lưu toàn bộ mảng dp kích thước N, ta chỉ cần giữ lại 2 giá trị gần nhất (dp[i-1] và dp[i-2]) để tính dp[i]. Điều này giảm đáng kể bộ nhớ sử dụng (từ O(N) xuống O(1) nếu không tính độ dài chuỗi số).
Cách Duyệt mảng đánh dấu
#include <bits/stdc++.h>
using namespace std;
string add(string a, string b) {
while (a.size() < b.size()) a = '0' + a;
while (a.size() > b.size()) b = '0' + b;
string res = "";
int carry = 0;
for (int i = a.size() - 1; i >= 0; i--) {
int digit = (a[i] - '0') + (b[i] - '0') + carry;
carry = digit / 10;
digit %= 10;
res = char(digit + '0') + res;
}
if (carry) res = '1' + res;
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
// Sử dụng mảng đánh dấu thay vì vector<bool> để dễ thao tác
// Tăng kích thước lên 1 chút để tránh lỗi truy cập ngoài
bool blocked[2005] = {false};
for (int i = 0; i < k; i++) {
int x;
cin >> x;
blocked[x] = true;
}
string prev2 = "0"; // dp[i-2]
string prev1 = "0"; // dp[i-1]
string current = "0";
// Xử lý trường hợp đặc biệt n=0
if (n == 0) {
cout << "1" << endl;
return 0;
}
// Khởi tạo cho bậc 0
prev2 = "1";
// Khởi tạo cho bậc 1
if (!blocked[1]) prev1 = "1";
else prev1 = "0";
if (n == 1) {
cout << prev1 << endl;
return 0;
}
// Duyệt từ 2 đến n
for (int i = 2; i <= n; i++) {
if (blocked[i]) {
current = "0";
} else {
current = add(prev1, prev2);
}
prev2 = prev1;
prev1 = current;
}
cout << current << endl;
return 0;
}
- Time Complexity: O(N * L)
- Space Complexity: O(L)
Đây là cách viết lại của phương pháp tối ưu bộ nhớ, sử dụng mảng static để đánh dấu các bậc thang bị hỏng. Logic tính toán hoàn toàn giống cách 2.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * L), với L là độ dài của số lớn (tối đa ~250) | O(N * L) | Quy hoạch động cơ bản với số lớn |
| 2 | O(N * L) | O(L) | Tối ưu bộ nhớ |
| 3 | O(N * L) | O(L) | Duyệt mảng đánh dấu |
Bài học kinh nghiệm
- Bài toán có cấu trúc quy hoạch động tuyến tính: Số cách lên bậc i phụ thuộc vào số cách lên các bậc i-1 và i-2.
- Vì số lượng cách lớn (lên đến 250 chữ số), bắt buộc phải sử dụng kiểu dữ liệu chuỗi (string) để lưu trữ và tự implement phép cộng số lớn.
- Chỉ cần sử dụng 3 biến lưu trữ chuỗi (prev2, prev1, current) là đủ để tính toán mà không cần mảng lớn.
Lỗi thường gặp
- Quên kiểm tra xem bậc thang hiện tại có bị hỏng không trước khi tính toán. Nếu hỏng thì số cách bằng 0.
- Xử lý sai trường hợp cơ sở: Bậc 0 (sân) có 1 cách, bậc 1 bị hỏng thì không thể lên.
- Lỗi truy cập mảng: Nếu sử dụng mảng đánh dấu, cần đảm bảo mảng có kích thước đủ lớn (>= N+1).
Bình luận