Hướng dẫn giải của Di chuyển
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 move: Di chuyển
Hiểu bài toán
Bài toán yêu cầu tìm đường đi từ ô (1, 1) đến ô (m, n) trên một bảng m × n sao cho tổng giá trị các ô trên đường đi là lớn nhất. Tại mỗi bước, chỉ được phép di chuyển sang phải (tăng cột) hoặc xuống dưới (tăng hàng). Đây là bài toán quy hoạch động kinh điển.
Các cách tiếp cận
Cách Quy hoạch động cơ bản (DP 2 chiều)
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
int main() {
int m,n;
scanf("%d%d",&m,&n);
int dp[600][600];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
scanf("%d",&dp[i][j]);
}
}
int a[600][600]={0};
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0&&j==0) a[i][j]=dp[i][j];
else if(i==0){
a[i][j]=a[i][j-1]+dp[i][j];
}
else if(j==0){
a[i][j]=a[i-1][j]+dp[i][j];
}
else{
a[i][j]=dp[i][j]+((a[i][j-1]>a[i-1][j])?a[i][j-1]:a[i-1][j]);
}
}
}
printf("%d\n",a[m-1][n-1]);
return 0;
}
- Time Complexity: O(m × n)
- Space Complexity: O(m × n)
Giải pháp sử dụng bảng 2 chiều a để lưu tổng lớn nhất đến từng ô. Với mỗi ô (i, j):
- Nếu là ô đầu tiên (0,0): giữ nguyên giá trị
- Nếu là hàng đầu tiên (i=0): chỉ có thể đến từ trái
- Nếu là cột đầu tiên (j=0): chỉ có thể đến từ trên
- Ngược lại: chọn max giữa đường từ trên xuống và đường từ trái sang Cuối cùng in ra giá trị tại ô (m-1, n-1).
Cách Quy hoạch động tối ưu (Indexing 1-based)
#include <stdio.h>
#define MAX_SIZE 501
int n, m;
int a[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][MAX_SIZE];
void solution(){
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
}
dp[1][1] = a[1][1];
for(int i = 2; i <= n; ++i) dp[i][1] = dp[i-1][1] + a[i][1];
for(int j = 2; j <= m; ++j) dp[1][j] = dp[1][j-1] + a[1][j];
for(int i = 2; i <= n; ++i){
for(int j = 2; j <= m; ++j){
dp[i][j] = (dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + a[i][j];
}
}
printf("%d", dp[n][m]);
}
int main(){
solution();
return 0;
}
- Time Complexity: O(m × n)
- Space Complexity: O(m × n)
Giải pháp tương tự nhưng sử dụng indexing 1-based (bắt đầu từ 1 thay vì 0). Điều này giúp code gọn hơn và tránh lỗi off-by-one. DP[i][j] lưu tổng lớn nhất đến ô (i,j). Khởi tạo riêng hàng đầu tiên và cột đầu tiên, sau đó tính toán các ô còn lại bằng cách chọn max từ trên hoặc trái cộng với giá trị ô hiện tại.
Cách Quy hoạch động tại chỗ (In-place DP)
#include<stdio.h>
#include<math.h>
int dx[2] = {0, -1};
int dy[2] = {-1, 0};
int main(){
int n, m;
scanf("%d%d", &n, &m);
int a[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
scanf("%d", &a[i][j]);
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
int max = -1e9;
for(int k=0; k<2; k++){
int i1 = i + dx[k];
int j1 = j + dy[k];
if(i1>=0 && i1<n && j1>=0 && j1<m)
max = fmax(max, a[i1][j1]);
}
if(i!=0 || j!=0)
a[i][j] += max;
}
}
printf("%d", a[n-1][m-1]);
}
- Time Complexity: O(m × n)
- Space Complexity: O(1) additional
Giải pháp tối ưu không gian bằng cách sử dụng trực tiếp mảng input a để lưu kết quả DP. Dùng mảng offset dx, dy để truy cập ô trước đó. Với mỗi ô (i,j), tính max từ các ô có thể đi tới (trên và trái), rồi cộng vào giá trị hiện tại. Điều kiện if(i!=0 || j!=0) để không thay đổi ô đầu tiên.
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 cơ bản (DP 2 chiều) |
| 2 | O(m × n) | O(m × n) | Quy hoạch động tối ưu (Indexing 1-based) |
| 3 | O(m × n) | O(1) additional | Quy hoạch động tại chỗ (In-place DP) |
Bài học kinh nghiệm
- Bài toán có tính chất tối ưu con bài toán con: tổng lớn nhất đến (i,j) phụ thuộc vào tổng lớn nhất đến các ô kề trước đó
- Chỉ cần xét 2 hướng di chuyển: từ trái sang và từ trên xuống
- Có thể tối ưu không gian bằng cách ghi đè lên mảng input
Lỗi thường gặp
- Quên xử lý trường hợp ô đầu tiên (0,0) hoặc biên bảng
- Sử dụng sai thứ tự hàng/cột (m là hàng, n là cột)
- Tràn số nếu dùng int cho tổng (cần long long với dữ liệu lớn)
Bình luận