Hiểu bài toán

Bài toán Tom và Jerry (tên file jerry.inp/jerry.out) là một bài toán về đồ thị/ma trận. Ta được cấp một ma trận (grid) kích thước N x M, mỗi ô có một giá trị (có thể là số nguyên, có thể là 0 hoặc âm). Jerry bắt đầu tại ô (0, 0) và cần đi đến ô (N-1, M-1). Jerry có thể di chuyển sang phải hoặc xuống dưới. Mục tiêu là tìm đường đi từ (0,0) đến (N-1, M-1) sao cho tổng giá trị các ô đi qua là lớn nhất có thể. Đây là bài toán quy hoạch động kinh điển (Dynamic Programming - DP) trên ma trận.

Các cách tiếp cận

Cách Quy hoạch động (Dynamic Programming)

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ifstream fin("jerry.inp");
    ofstream fout("jerry.out");

    int n, m;
    if (!(fin >> n >> m)) return 0;

    vector<vector<long long>> dp(n, vector<long long>(m));

    // Đọc dữ liệu và xây dựng bảng DP
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            long long val;
            fin >> val;

            if (i == 0 && j == 0) {
                dp[i][j] = val;
            } else if (i == 0) {
                dp[i][j] = dp[i][j-1] + val;
            } else if (j == 0) {
                dp[i][j] = dp[i-1][j] + val;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + val;
            }
        }
    }

    fout << dp[n-1][m-1] << endl;

    fin.close();
    fout.close();
    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(N * M)

Đây là cách tiếp cận trực tiếp và tối ưu nhất cho bài toán này (trừ khi ma trận quá lớn, nhưng trong khuôn khổ thi đấu phổ thông thì đây là đáp án).

1. Tạo một ma trận DP cùng kích thước N x M.
2. dp[i][j] lưu tổng giá trị lớn nhất có thể đạt được khi đi từ (0,0) đến (i, j).
3. Công thức truy hồi:
   • Tại vị trí (0,0): dp[0][0] = grid[0][0].
   • Tại hàng đầu tiên (i=0, j>0): Chỉ có thể đi ngang sang phải từ ô bên trái. dp[0][j] = dp[0][j-1] + grid[0][j].
   • Tại cột đầu tiên (i>0, j=0): Chỉ có thể đi xuống từ ô bên trên. dp[i][0] = dp[i-1][0] + grid[i][0].
   • Các vị trí còn lại: Có thể đến từ ô bên trên hoặc ô bên trái. Ta chọn ô nào cho tổng lớn hơn. dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j].
4. Giá trị trả về là dp[N-1][M-1]. Lưu ý: Nên dùng long long để tránh tràn số nếu tổng giá trị lớn.

Cách Quy hoạch động tối ưu không gian (Space Optimized DP)

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ifstream fin("jerry.inp");
    ofstream fout("jerry.out");

    int n, m;
    if (!(fin >> n >> m)) return 0;

    // Chỉ cần lưu 2 hàng (hoặc 2 cột) để tiết kiệm bộ nhớ
    vector<vector<long long>> dp(2, vector<long long>(m));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            long long val;
            fin >> val;

            int row = i % 2;
            int prev_row = 1 - row;

            if (i == 0 && j == 0) {
                dp[row][j] = val;
            } else if (i == 0) {
                dp[row][j] = dp[row][j-1] + val;
            } else if (j == 0) {
                dp[row][j] = dp[prev_row][j] + val;
            } else {
                dp[row][j] = max(dp[prev_row][j], dp[row][j-1]) + val;
            }
        }
    }

    fout << dp[(n-1) % 2][m-1] << endl;

    fin.close();
    fout.close();
    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(M)

Cách tiếp cận này giống về logic với cách 1 nhưng tối ưu về bộ nhớ. Khi tính toán dp[i][j], ta chỉ cần thông tin từ hàng i-1 (trên) và các ô đã tính ở hàng i (trái). Do đó, ta không cần lưu toàn bộ ma trận N x M.

• Ta chỉ cần một mảng 1 chiều (hoặc ma trận 2xM).
• dp[j] (hoặc dp[1%2][j]) sẽ lưu giá trị tốt nhất tại hàng hiện tại.
• dp[j] (hoặc dp[0%2][j]) sẽ lưu giá trị tốt nhất tại hàng trước đó. Cách này giảm đáng kể bộ nhớ nếu N và M lớn (ví dụ N=10^5, M=10^5 nhưng tổng N*M không vượt quá giới hạn đọc file).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có cấu trúc tối ưu con (optimal substructure) và tính bắc cầu (overlapping subproblems), nên có thể áp dụng Quy hoạch động (DP).
• Tại mỗi ô (i, j), đường đi tốt nhất để đến đó phải là đường đi tốt nhất từ một trong hai ô lân cận (trên hoặc trái).
• Cần chú ý đến các trường hợp biên (hàng đầu tiên và cột đầu tiên) vì chỉ có một hướng di chuyển duy nhất.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Nếu tổng giá trị các ô lớn, biến int có thể bị tràn. Nên dùng long long (hoặc int64_t).
• Lỗi truy cập ngoài mảng: Khi i=0 hoặc j=0, không được truy cập dp[i-1][j] hoặc dp[i][j-1].
• Quên khởi tạo giá trị cho ô bắt đầu (0,0) hoặc xử lý sai thứ tự duyệt (phải duyệt theo thứ tự từ trái sang phải, từ trên xuống dưới).