Hướng dẫn giải của Gà Con
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ìm đường đi từ hàng 1 đến hàng N của một ma trận N x M sao cho tổng số thóc (giá trị các ô) trên đường đi là lớn nhất. Con gà bắt đầu tại bất kỳ ô nào trên hàng 1 và di chuyển xuống dưới. Tại mỗi bước từ hàng i sang hàng i+1, con gà có thể di chuyển thẳng xuống (cột giữ nguyên), hoặc chéo trái (cột giảm 1), hoặc chéo phải (cột tăng 1). Ta cần tính tổng thóc lớn nhất có thể thu được.
Các cách tiếp cận
Cách Quy hoạch động cơ bản
#include <bits/stdc++.h>
using namespace std;
long long a[1001][1001], f[1001][1001];
int n, m, i, j;
int main() {
cin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
cin >> a[i][j];
for (j = 1; j <= m; j++)
f[1][j] = a[1][j];
for (i = 2; i <= n; i++)
for (j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j] + a[i][j];
if (j > 1) f[i][j] = max(f[i][j], f[i - 1][j - 1] + a[i][j]);
if (j < m) f[i][j] = max(f[i][j], f[i - 1][j + 1] + a[i][j]);
}
long long res = 0;
for (j = 1; j <= m; j++)
res = max(res, f[n][j]);
cout << res;
return 0;
}
- Time Complexity: O(N x M)
- Space Complexity: O(N x M)
Sử dụng mảng 2 chiều f[i][j] để lưu tổng thóc lớn nhất có thể吃到 được khi đến ô (i, j). Công thức truy hồi: f[i][j] = a[i][j] + max(f[i-1][j], f[i-1][j-1], f[i-1][j+1]). Sau cùng, duyệt hàng cuối để tìm giá trị lớn nhất. Cách này dễ hiểu nhưng tốn bộ nhớ.
Cách Quy hoạch động tối ưu không gian
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<vector<long long>> a(N, vector<long long>(M));
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cin >> a[i][j];
vector<long long> dp_prev(M), dp_cur(M);
for (int j = 0; j < M; j++)
dp_prev[j] = a[0][j];
for (int i = 1; i < N; i++) {
for (int j = 0; j < M; j++) {
long long best = dp_prev[j];
if (j > 0) best = max(best, dp_prev[j - 1]);
if (j + 1 < M) best = max(best, dp_prev[j + 1]);
dp_cur[j] = best + a[i][j];
}
swap(dp_prev, dp_cur);
}
long long ans = 0;
for (long long x : dp_prev) ans = max(ans, x);
cout << ans;
return 0;
}
- Time Complexity: O(N x M)
- Space Complexity: O(M)
Vì để tính hàng i ta chỉ cần thông tin từ hàng i-1, ta có thể tối ưu không gian bằng cách chỉ dùng 2 mảng 1 chiều: dp_prev (lưu kết quả hàng trước) và dp_cur (tính kết quả hàng hiện tại). Sau mỗi hàng, ta cập nhật lại dp_prev. Cách này giảm đáng kể bộ nhớ sử dụng.
Cách Quy hoạch động với mảng 1 chiều
#include <bits/stdc++.h>
using namespace std;
int a[1000][1000], dp[1005][1005];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
long long n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int j = 1; j <= m; j++)
dp[1][j] = a[1][j];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int di = -1; di <= 1; di++) {
int k = j + di;
if (k >= 1 && k <= m) {
if (dp[i - 1][k] + a[i][j] > dp[i][j]) {
dp[i][j] = dp[i - 1][k] + a[i][j];
}
}
}
}
}
long long ans = 0;
for (int j = 1; j <= m; j++)
if (dp[n][j] > ans) ans = dp[n][j];
cout << ans << '\n';
return 0;
}
- Time Complexity: O(N x M)
- Space Complexity: O(N x M)
Đây là cách tiếp cận quy hoạch động tiêu chuẩn với mảng 2 chiều. Logic tương tự cách 1 nhưng cách viết code có thể khác nhau một chút (ví dụ dùng vòng lặp di thay vì if rời rạc). Tuy nhiên về bản chất vẫn là lưu trữ toàn bộ bảng quy hoạch động, tốn bộ nhớ O(N*M).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N x M) | O(N x M) | Quy hoạch động cơ bản |
| 2 | O(N x M) | O(M) | Quy hoạch động tối ưu không gian |
| 3 | O(N x M) | O(N x M) | Quy hoạch động với mảng 1 chiều |
Bài học kinh nghiệm
- Bài toán có tính chất quy hoạch động: giá trị tối ưu tại ô
(i, j)phụ thuộc vào các ô ở hàngi-1. - Có thể tối ưu không gian từ O(N*M) xuống O(M) bằng cách chỉ lưu trữ kết quả của hàng trước đó.
Lỗi thường gặp
- Quên kiểm tra biên (khi j=1 hoặc j=M) khi truy cập các ô chéo trái/phải.
- Sử dụng sai kiểu dữ liệu (nên dùng
long longvì tổng thóc có thể lớn, tối đa khoảng 10^5 * 10^6 = 10^11).
Bình luận