Thu thập điểm tối đa trong lưới bằng hai lần duyệt

Cho một ma trận với điểm ở mỗi ô, bài toán yêu cầu tìm tổng điểm tối đa có thể thu được bằng hai lần duyệt qua lưới, tuân theo các điều kiện sau:

• Lượt duyệt thứ nhất bắt đầu từ góc trên bên trái và kết thúc ở góc dưới bên trái.
• Lượt duyệt thứ hai bắt đầu từ góc trên bên phải và kết thúc ở góc dưới bên phải.
• Từ một ô, chỉ được di chuyển xuống dưới, xuống chéo trái hoặc xuống chéo phải so với ô hiện tại.
• Nếu một lượt duyệt đã lấy điểm từ một ô, lượt duyệt còn lại sẽ không nhận điểm từ ô đó nữa.

Đầu vào và Đầu ra

Đầu vào: Lưới điểm. Ví dụ ma trận 5x4:
3 6 8 2
5 2 4 3
1 1 20 10
1 1 20 10
1 1 20 10

Đầu ra: Tổng điểm tối đa là 73.
Lượt 1: 3 + 2 + 20 + 1 + 1 = 27
Lượt 2: 2 + 4 + 10 + 20 + 10 = 46

Thuật toán

Sử dụng quy hoạch động vớimemorization (bảng ghi nhớ 3 chiều). Hàm findMaxVal(mTable, x, y1, y2) trả về điểm tối đa từ hàng x khi lượt 1 ở cột y1 và lượt 2 ở cột y2.

Các trường hợp cơ sở:

• Nếu tọa độ không hợp lệ → trả về -∞.
• Nếu cả hai lượt đã hoàn thành (đến hàng cuối cùng và đúng cột đích) → trả về điểm ô hiện tại (cộng cả hai nếu khác cột).
• Nếu đã đến hàng cuối nhưng chưa hoàn thành → trả về -∞.
• Nếu bài toán con đã giải → trả về giá trị trong mTable.

Quy hoạch động: Thử tất cả 9 tổ hợp di chuyển hợp lệ cho hai lượt (mỗi lượt có 3 hướng: xuống, chéo trái, chéo phải), lấy giá trị lớn nhất, lưu vào mTable và trả về.

Ví dụ C++

#include <iostream>
#define ROW 5
#define COL 4
using namespace std;

int grid[ROW][COL] = {
    {3, 6, 8, 2},
    {5, 2, 4, 3},
    {1, 1, 20, 10},
    {1, 1, 20, 10},
    {1, 1, 20, 10}
};

bool isValidInput(int x, int y1, int y2) {
    return (x >= 0 && x < ROW && y1 >= 0 && y1 < COL && y2 >= 0 && y2 < COL);
}

int findMaxVal(int mTable[ROW][COL][COL], int x, int y1, int y2) {
    if (!isValidInput(x, y1, y2)) return INT_MIN;
    if (x == ROW-1 && y1 == 0 && y2 == COL-1)
        return (y1 == y2) ? grid[x][y1] : grid[x][y1] + grid[x][y2];
    if (x == ROW-1) return INT_MIN;
    if (mTable[x][y1][y2] != -1) return mTable[x][y1][y2];

    int temp = (y1 == y2) ? grid[x][y1] : grid[x][y1] + grid[x][y2];
    int ans = INT_MIN;

    ans = max(ans, temp + findMaxVal(mTable, x+1, y1,   y2-1));
    ans = max(ans, temp + findMaxVal(mTable, x+1, y1,   y2));
    ans = max(ans, temp + findMaxVal(mTable, x+1, y1,   y2+1));
    ans = max(ans, temp + findMaxVal(mTable, x+1, y1-1, y2-1));
    ans = max(ans, temp + findMaxVal(mTable, x+1, y1-1, y2));
    ans = max(ans, temp + findMaxVal(mTable, x+1, y1-1, y2+1));
    ans = max(ans, temp + findMaxVal(mTable, x+1, y1+1, y2-1));
    ans = max(ans, temp + findMaxVal(mTable, x+1, y1+1, y2));
    ans = max(ans, temp + findMaxVal(mTable, x+1, y1+1, y2+1));

    return mTable[x][y1][y2] = ans;
}

int findMaxCollection() {
    int mTable[ROW][COL][COL];
    for(int i=0;i<ROW;i++) for(int j=0;j<COL;j++) for(int k=0;k<COL;k++) mTable[i][j][k] = -1;
    return findMaxVal(mTable, 0, 0, COL-1);
}

int main() {
    cout << "Maximum collection is " << findMaxCollection();
    return 0;
}

Kết quả

Maximum collection is 73