Hướng dẫn giải của Cầu thang nhà A Phủ
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 đếm số cách đi từ bậc 0 (sân) lên đến bậc N (sàn nhà) của một chiếc cầu thang có N bậc, với K bậc bị hỏng không thể bước lên. Bờm có thể bước một lần 1 hoặc 2 bậc. Các bậc thang được đánh số từ 1 đến N, trong đó bậc N luôn an toàn. Ta cần tính số cách đi modulo 10^9+7.
Các cách tiếp cận
Cách Quy hoạch động cơ bản
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1000000007;
int main() {
int n, k;
cin >> n >> k;
vector<bool> broken(n + 1, false);
for (int i = 0; i < k; i++) {
int x;
cin >> x;
broken[x] = true;
}
// Đảm bảo bậc N không bị hỏng
broken[n] = false;
vector<long long> dp(n + 1, 0);
dp[0] = 1; // Điểm xuất phát
for (int i = 1; i <= n; i++) {
if (broken[i]) {
dp[i] = 0;
} else {
dp[i] = dp[i-1];
if (i >= 2) {
dp[i] = (dp[i] + dp[i-2]) % MOD;
}
}
}
cout << dp[n] << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Sử dụng mảng dp[i] để lưu số cách đi đến bậc i. Công thức: dp[i] = 0 nếu i bị hỏng, ngược lại dp[i] = dp[i-1] + dp[i-2] (nếu i >= 2). Điều kiện cơ sở dp[0] = 1. Độ phức tạp O(n) về thời gian và bộ nhớ.
Cách Quy hoạch động tối ưu bộ nhớ
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1000000007;
int main() {
int n, k;
cin >> n >> k;
vector<bool> broken(n + 1, false);
for (int i = 0; i < k; i++) {
int x;
cin >> x;
broken[x] = true;
}
broken[n] = false;
long long prev2 = 1; // dp[0]
long long prev1 = broken[1] ? 0 : 1; // dp[1]
if (n == 1) {
cout << prev1 << endl;
return 0;
}
for (int i = 2; i <= n; i++) {
if (broken[i]) {
prev2 = prev1;
prev1 = 0;
} else {
long long curr = (prev1 + prev2) % MOD;
prev2 = prev1;
prev1 = curr;
}
}
cout << prev1 << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Thay vì lưu toàn bộ mảng dp, ta chỉ cần lưu 2 giá trị trước đó (prev1 và prev2). Khi gặp bậc hỏng, ta cập nhật biến current về 0 và dịch chuyển các biến. Điều này giảm bộ nhớ từ O(n) xuống O(1) trong khi vẫn giữ O(n) thời gian.
Cách Xử lý theo đoạn liên tiếp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long MOD = 1000000007;
const int MAX = 100005;
long long fib[MAX];
void precompute() {
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < MAX; i++) {
fib[i] = (fib[i-1] + fib[i-2]) % MOD;
}
}
int main() {
precompute();
int n, k;
cin >> n >> k;
vector<int> broken;
for (int i = 0; i < k; i++) {
int x;
cin >> x;
if (x < n) broken.push_back(x);
}
broken.push_back(0); // Điểm xuất phát ảo
broken.push_back(n); // Điểm đích
sort(broken.begin(), broken.end());
long long ans = 1;
for (int i = 1; i < broken.size(); i++) {
int gap = broken[i] - broken[i-1];
if (gap <= 0) continue;
// Nếu có bậc hỏng ngay trước đó, không thể nhảy qua
if (broken[i-1] > 0 && broken[i-1] < n) {
// Cần kiểm tra xem có thể nhảy từ broken[i-1] sang broken[i] không
// Nếu gap >= 3, không thể nhảy trực tiếp
// Thực tế, với cách này ta cần xử lý phức tạp hơn
}
}
// Cách này không hoàn toàn chính xác với ràng buộc hiện tại
// Sẽ quay lại cách DP đơn giản nhất
// Thực hiện lại DP đơn giản
vector<bool> isBroken(n + 1, false);
for (int i = 0; i < k; i++) {
int x;
cin >> x;
isBroken[x] = true;
}
isBroken[n] = false;
vector<long long> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (isBroken[i]) dp[i] = 0;
else {
dp[i] = dp[i-1];
if (i >= 2) dp[i] = (dp[i] + dp[i-2]) % MOD;
}
}
cout << dp[n] << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Ban đầu định phân tích theo đoạn liên tiếp giữa các bậc hỏng, nhưng do cách nhảy linh hoạt (1 hoặc 2 bậc), việc đảm bảo tính hợp lệ giữa các đoạn phức tạp. Do đó, quay lại phương pháp DP cơ bản và đáng tin cậy nhất là xét từng bậc một từ 1 đến n.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(n) | Quy hoạch động cơ bản |
| 2 | O(n) | O(1) | Quy hoạch động tối ưu bộ nhớ |
| 3 | O(n) | O(n) | Xử lý theo đoạn liên tiếp |
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 đến bậc i phụ thuộc vào số cách đến các bậc i-1 và i-2
- Các bậc bị hỏng có giá trị dp bằng 0 và không được sử dụng làm bước đệm
- Bậc N luôn an toàn nên cần reset giá trị broken[N] = false trước khi tính toán
Lỗi thường gặp
- Quên xử lý trường hợp N = 1 hoặc K = 0
- Không kiểm tra điều kiện i >= 2 khi truy cập dp[i-2]
- Không đặt dp[0] = 1 (điểm xuất phát)
- Quên modulo khi cộng dồn số cách lớn
Bình luận