Hướng dẫn giải của Đường đi có tổng lớn nhất
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ừ một ô bất kỳ ở cột đầu tiên (cột 1) đến một ô bất kỳ ở cột cuối cùng (cột n) trên một bảng m x n sao cho tổng các số trên đường đi là lớn nhất. Quy tắc di chuyển: từ ô (i, j), có thể di chuyển sang ô (i, j+1) (ngang), (i-1, j+1) (chéo lên), hoặc (i+1, j+1) (chéo xuống). Ta cần tính tổng lớn nhất có thể.
Các cách tiếp cận
Cách Quy hoạch động (Từ trái sang phải)
#include <stdio.h>
#include <limits.h>
const int MAX = 100;
int max(int a, int b, int c) {
int x = a;
if (x < b) x = b;
if (x < c) x = c;
return x;
}
int main(void) {
int m, n;
scanf("%d%d", &m, &n);
int a[MAX][MAX];
int dp[MAX][MAX];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
}
}
// Khởi tạo cột đầu tiên
for (int i = 0; i < m; i++) {
dp[i][0] = a[i][0];
}
// Duyệt qua từng cột từ cột 1 đến cột n-1
for (int j = 1; j < n; j++) {
for (int i = 0; i < m; i++) {
int tren = (i > 0) ? dp[i-1][j-1] : INT_MIN;
int giua = dp[i][j-1];
int duoi = (i < m-1) ? dp[i+1][j-1] : INT_MIN;
dp[i][j] = max(tren, giua, duoi) + a[i][j];
}
}
int Max = dp[0][n-1];
for (int i = 1; i < m; i++) {
if (Max < dp[i][n-1]) Max = dp[i][n-1];
}
printf("%d", Max);
return 0;
}
- Time Complexity: O(m * n)
- Space Complexity: O(m * n)
Cách tiếp cận này sử dụng quy hoạch động. Ta định nghĩa dp[i][j] là tổng lớn nhất của đường đi kết thúc tại ô (i, j). Công thức truy hồi: dp[i][j] = a[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1]). Ta khởi tạo cột đầu tiên, sau đó điền vào bảng dp từ trái sang phải. Kết quả là giá trị lớn nhất ở cột cuối cùng của bảng dp. Các ô biên được xử lý bằng cách gán giá trị âm vô cùng (INT_MIN) để loại trừ đường đi không hợp lệ.
Cách Quy hoạch động (Từ phải sang trái)
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>
#define max(x, y) (x > y ? x : y)
int main(){
int m,n;
scanf("%d %d",&m,&n);
int a[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++) scanf("%d",&a[i][j]);
}
int dp[m][n];
// Khởi tạo cột cuối cùng
for(int i=0;i<m;i++){
dp[i][n-1]=a[i][n-1];
}
// Duyệt từ cột áp cuối về cột đầu
for(int i=n-2;i>=0;i--){
for(int j=0;j<m;j++){
dp[j][i]=a[j][i]+dp[j][i+1];
if(j==0 && m>1) dp[j][i]=max(dp[j][i],dp[j+1][i+1]+a[j][i]);
else if(j==m-1 && m>1) dp[j][i]=max(dp[j][i],dp[j-1][i+1]+a[j][i]);
else if(m>2) dp[j][i]=max( dp[j][i], max(dp[j-1][i+1],dp[j+1][i+1])+a[j][i] );
}
}
int kq=dp[0][0];
for(int i=0;i<m;i++){
kq=max(kq,dp[i][0]);
}
printf("%d",kq);
}
- Time Complexity: O(m * n)
- Space Complexity: O(m * n)
Cách tiếp cận này cũng là quy hoạch động nhưng được thực hiện theo chiều ngược lại, từ phải sang trái. Ta định nghĩa dp[i][j] là tổng lớn nhất của đường đi bắt đầu từ ô (i, j) và kết thúc tại cột cuối cùng. Ta khởi tạo cột cuối cùng, sau đó tính toán các cột trước đó dựa trên các ô ở cột bên phải. Kết quả là giá trị lớn nhất ở cột đầu tiên của bảng dp. Logic này tương đương với cách đi từ trái sang phải.
Cách Quy hoạch động (Optimized Space)
// Pseudocode for Space Optimized Approach
#include <stdio.h>
#include <limits.h>
int max(int a, int b, int c) {
int res = a;
if (b > res) res = b;
if (c > res) res = c;
return res;
}
int main() {
int m, n;
scanf("%d %d", &m, &n);
int prev[m]; // Chỉ cần lưu cột trước đó
int curr[m]; // Cột hiện tại
int val;
// Đọc và khởi tạo cột đầu tiên
for (int i = 0; i < m; i++) {
scanf("%d", &val);
prev[i] = val;
}
// Duyệt các cột tiếp theo
for (int j = 1; j < n; j++) {
for (int i = 0; i < m; i++) {
scanf("%d", &val);
int top = (i > 0) ? prev[i-1] : INT_MIN;
int mid = prev[i];
int bot = (i < m - 1) ? prev[i+1] : INT_MIN;
curr[i] = max(top, mid, bot) + val;
}
// Sao chép curr vào prev cho lượt tiếp theo
for (int i = 0; i < m; i++) {
prev[i] = curr[i];
}
}
int ans = prev[0];
for (int i = 1; i < m; i++) {
if (prev[i] > ans) ans = prev[i];
}
printf("%d", ans);
return 0;
}
- Time Complexity: O(m * n)
- Space Complexity: O(m)
Đây là phiên bản tối ưu hóa bộ nhớ của quy hoạch động. Thay vì lưu trữ toàn bộ bảng dp kích thước m x n, ta chỉ cần lưu trữ giá trị của cột trước đó (prev) để tính toán cột hiện tại (curr). Sau khi tính xong cột hiện tại, ta cập nhật prev để chuẩn bị cho cột tiếp theo. Cách này giảm đáng kể bộ nhớ sử dụng mà không làm tăng độ phức tạp thời gian.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(m * n) | O(m * n) | Quy hoạch động (Từ trái sang phải) |
| 2 | O(m * n) | O(m * n) | Quy hoạch động (Từ phải sang trái) |
| 3 | O(m * n) | O(m) | Quy hoạch động (Optimized Space) |
Bài học kinh nghiệm
- Bài toán có tính chất quy hoạch động: tổng lớn nhất tại một ô phụ thuộc vào tổng lớn nhất của các ô có thể đi đến nó (ở cột trước đó).
- Có thể giải quyết theo 2 hướng: từ trái sang phải (tính dp[i][j] dựa trên cột j-1) hoặc từ phải sang trái (tính dp[i][j] dựa trên cột j+1).
- Việc xử lý các ô biên (trên cùng, dưới cùng) là quan trọng để tránh truy cập ngoài mảng và đảm bảo đường đi hợp lệ.
Lỗi thường gặp
- Quên kiểm tra điều kiện biên (i == 0 hoặc i == m-1) dẫn đến lỗi truy cập mảng.
- Gán sai giá trị âm vô cùng (INT_MIN) cho các ô không thể đi tới, dẫn đến việc tính toán sai nếu đường đi bắt buộc phải qua các ô này.
- Lỗi thứ tự vòng lặp: phải đảm bảo tính toán xong tất cả các ô ở cột trước trước khi chuyển sang cột sau.
Bình luận