หาคะแนนสูงสุดในกริดโดยใช้การเดินทาง 2 ครั้ง

มีเมทริกซ์ที่แต่ละเซลล์มีคะแนน จุดประสงค์คือการหาคะแนนสูงสุดที่สามารถเก็บได้จากกริดนี้โดยใช้การเดินทาง 2 ครั้ง โดยมีเงื่อนไขดังนี้:

เงื่อนไขของปัญหา

• การเดินทางครั้งที่ 1: เริ่มจากมุมซ้ายบน (0,0) และต้องไปถึงมุมซ้ายล่าง
• การเดินทางครั้งที่ 2: เริ่มจากมุมขวาบน และต้องไปถึงมุมขวาล่าง
• การเคลื่อนที่: จากเซลล์หนึ่งสามารถเคลื่อนที่ได้เฉพาะไปข้างล่าง, ล่างซ้าย, หรือ ล่างขวาของเซลล์ปัจจุบันเท่านั้น
• กฎการให้คะแนน: หากการเดินทางครั้งแรกได้คะแนนจากเซลล์ใดแล้ว การเดินทางครั้งที่สองจะไม่ได้คะแนนจากเซลล์นั้นอีก

ตัวอย่าง Input และ Output

Input: กริดขนาด 5x4
3  6  8  2
5  2  4  3
1  1 20 10
1  1 20 10
1  1 20 10

Output: คะแนนสูงสุดที่เก็บได้จาก 2 การเดินทางคือ 73
- การเดินทางครั้งที่ 1 ได้: 3 + 2 + 20 + 1 + 1 = 27
- การเดินทางครั้งที่ 2 ได้: 2 + 4 + 10 + 20 + 10 = 46

อัลกอริทึม (Dynamic Programming with Memoization)

ใช้ฟังก์ชัน findMaxVal(mTable, x, y1, y2) โดยที่:

• mTable: ตาราง 3 มิติสำหรับ Memoization
• x: แถวปัจจุบัน (ทั้ง 2 การเดินทางอยู่แถวเดียวกันเสมอ)
• y1: คอลัมน์ของการเดินทางครั้งที่ 1
• y2: คอลัมน์ของการเดินทางครั้งที่ 2

ขั้นตอนหลัก:

1. Base Case - Invalid: หากพิกัดไม่อยู่ในกริด → คืนค่า -∞
2. Base Case - เสร็จสิ้น: ถ้าทั้งสองถึงแถวสุดท้ายและ y1=0, y2=COL-1:
   • ถ้า y1 == y2 (อยู่เซลล์เดียวกัน) → คืนค่า grid[x][y1]
   • ถ้าไม่ใช่เซลล์เดียวกัน → คืนค่า grid[x][y1] + grid[x][y2]
3. Base Case - ถึงแถวสุดท้ายแต่ยังไม่เสร็จ: คืนค่า -∞
4. Memoization: หาก mTable[x][y1][y2] คำนวณแล้ว → คืนค่าทันที
5. คำนวณคะแนนปัจจุบัน:
   • ถ้า y1 == y2 → temp = grid[x][y1]
   • ถ้า y1 != y2 → temp = grid[x][y1] + grid[x][y2]
6. สำรวจ 9 ทิศทาง: ทั้งคู่เคลื่อนที่ลงแถวถัดไป (x+1) โดย y1 และ y2 แต่ละอันสามารถอยู่ที่เดิม, ซ้าย, หรือขวา → รวม 3×3 = 9 กรณี
7. เลือกค่าสูงสุด จาก 9 กรณี บวกกับ temp → เก็บใน mTable และคืนค่า

ตัวอย่างโค้ด 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 ans = INT_MIN;
    int temp = (y1 == y2) ? grid[x][y1] : grid[x][y1] + grid[x][y2];

    // 9 ทิศทางที่เป็นไปได้
    ans = max(ans, temp + findMaxVal(mTable, x+1, y1,   y2-1));
    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-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));
    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;
}

Output

Maximum collection is 73

ความซับซ้อนของเวลา

O(ROW × COL²) เนื่องจากมีสถานะทั้งหมด ROW × COL × COL สถานะ และแต่ละสถานะคำนวณเพียงครั้งเดียว