Hướng dẫn giải của Lát gạch
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
, , ,
Editorial for latgach: Lát gạch
Hiểu bài toán
Bài toán yêu cầu đếm số cách lát một hình chữ nhật kích thước 2×N bằng các viên gạch 1×2 (ngang) và 2×1 (dọc). Đây là bài toán kinh điển về dãy Fibonacci. Với mỗi cột i, ta có thể đặt:
- Một viên gạch dọc (2×1): khi đó phần còn lại là 2×(i-1).
- Hai viên gạch ngang (1×2) chồng lên nhau: khi đó phần còn lại là 2×(i-2). Vậy số cách lát cho N cột là tổng số cách lát cho N-1 cột và N-2 cột. Quy hoạch động với dp[1] = 1, dp[2] = 2, dp[i] = dp[i-1] + dp[i-2].
Các cách tiếp cận
Cách Quy hoạch động cơ bản (Mảng)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int T;
cin >> T;
// Khởi tạo mảng dp với kích thước tối đa 91
vector<long long> dp(91);
dp[1] = 1;
dp[2] = 2;
// Tính toán trước các giá trị dp
for (int i = 3; i <= 90; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
while (T--) {
int N;
cin >> N;
cout << dp[N] << "\n";
}
return 0;
}
- Time Complexity: O(90) để tính toán ban đầu + O(T) để trả lời truy vấn, tổng thể O(1) (vì 90 là hằng số)
- Space Complexity: O(90) ~ O(1)
Sử dụng mảng 1 chiều để lưu trữ kết quả của các bài toán con. Tính toán các giá trị dp[1], dp[2], ..., dp[90] một lần trước khi xử lý các test case. Với mỗi test case, chỉ cần truy cập mảng để lấy kết quả.
Cách Quy hoạch động tối ưu (Không gian)
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int N;
cin >> N;
if (N == 0) {
cout << 0 << "\n";
continue;
}
if (N == 1) {
cout << 1 << "\n";
continue;
}
long long a = 1; // dp[i-2]
long long b = 2; // dp[i-1]
long long c;
for (int i = 3; i <= N; i++) {
c = a + b;
a = b;
b = c;
}
cout << b << "\n";
return 0;
}
- Time Complexity: O(N) cho mỗi test case
- Space Complexity: O(1)
Thay vì lưu trữ toàn bộ dãy Fibonacci, ta chỉ cần duy trì 2 biến lưu giá trị của 2 bước trước đó (a và b). Biến c dùng để tính toán giá trị mới. Kỹ thuật này tiết kiệm bộ nhớ đáng kể.
Cách Ma trận lũy thừa (Độ phức tạp Logarithmic)
#include <iostream>
#include <vector>
using namespace std;
struct Matrix {
long long mat[2][2];
Matrix() {
mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0;
}
};
Matrix multiply(Matrix A, Matrix B) {
Matrix C;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
C.mat[i][j] += A.mat[i][k] * B.mat[k][j];
}
}
}
return C;
}
Matrix power(Matrix A, int p) {
Matrix res;
res.mat[0][0] = 1; res.mat[1][1] = 1; // Ma trận đơn vị
while (p > 0) {
if (p & 1) res = multiply(res, A);
A = multiply(A, A);
p >>= 1;
}
return res;
}
int main() {
int T;
cin >> T;
// Ma trận cơ sở: [1, 1]
// [1, 0]
Matrix base;
base.mat[0][0] = 1; base.mat[0][1] = 1;
base.mat[1][0] = 1; base.mat[1][1] = 0;
while (T--) {
int N;
cin >> N;
if (N == 1) { cout << 1 << "\n"; continue; }
Matrix res = power(base, N - 1);
// Kết quả là số Fibonacci F(N+1) = F(N) + F(N-1)
// Công thức: F(n) = [1, 0] * T^(n-1) * [1, 0]^T
// Ở đây ta cần F(N) với F(1)=1, F(2)=1.
// Ta có dãy bài toán là 1, 2, 3, 5... (F3, F4...)
// N=1 -> 1. N=2 -> 2. N=3 -> 3.
// Ma trận trả về F(n+1) nếu tính từ F(1)=1, F(2)=1.
// Ta cần F(N) theo dãy 1, 1, 2, 3, 5... nhưng bài này là 1, 2, 3, 5...
// Dãy bài toán: a_n = a_{n-1} + a_{n-2}. a_1=1, a_2=2.
// Tương đương Fibonacci F_{n+1} (với F_1=1, F_2=1).
cout << res.mat[0][0] + res.mat[0][1] << "\n";
}
return 0;
}
- Time Complexity: O(log N) cho mỗi test case
- Space Complexity: O(1)
Sử dụng ma trận để tính số Fibonacci. Ma trận [[1, 1], [1, 0]]^(n-1) cho ra kết quả Fibonacci Fn và F{n-1}. Phương pháp này hiệu quả cho N rất lớn (siêu lớn), nhưng với N <= 90 thì không cần thiết.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(90) để tính toán ban đầu + O(T) để trả lời truy vấn, tổng thể O(1) (vì 90 là hằng số) | O(90) ~ O(1) | Quy hoạch động cơ bản (Mảng) |
| 2 | O(N) cho mỗi test case | O(1) | Quy hoạch động tối ưu (Không gian) |
| 3 | O(log N) cho mỗi test case | O(1) | Ma trận lũy thừa (Độ phức tạp Logarithmic) |
Bài học kinh nghiệm
- Bài toán có cấu trúc quy hoạch động: DP[i] = DP[i-1] + DP[i-2].
- Dãy số cần tìm là dãy Fibonacci mở rộng (F1=1, F2=2, F3=3...).
- Với N nhỏ (<= 90), chỉ cần tính toán trước và lưu vào mảng là đủ.
Lỗi thường gặp
- Lưu ý về kiểu dữ liệu: Số cách lát có thể lớn, cần dùng
long long(64-bit) để tránh tràn số. - Xử lý các trường hợp cơ sở (base cases) sai: N=1, N=2 phải được gán đúng giá trị trước khi vào vòng lặp.
- Độ phức tạp tính toán: Nếu tính lại từ đầu cho mỗi test case, tổng thời gian có thể vượt quá giới hạn nếu T lớn và N lớn. Tuy nhiên với T<=10 và N<=90, cách này vẫn an toàn.
Bình luận