หา Initial Points ขั้นต่ำเพื่อไปถึงจุดหมายในกริด

เริ่มจากมุมซ้ายบน (0,0) ของกริด ต้องไปถึงมุมขวาล่าง แต่ละเซลล์มีค่าตัวเลข (บวกหรือลบ) เมื่อเข้าถึงเซลล์ (i,j) โทเคนจะเพิ่ม/ลดตามค่านั้น ต้องการหา โทเคนเริ่มต้นน้อยที่สุด ที่ทำให้เดินทางสำเร็จ

กฎการเดินทาง

• เดินได้เฉพาะ ขวา หรือ ล่าง เท่านั้น
• ไม่สามารถเข้าสูงเซลล์ (i,j) ได้ถ้าโทเคนปัจจุบัน < ค่าของเซลล์นั้น
• ต้องถึงจุดหมายด้วยโทเคนบวก (อย่างน้อย 1)

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

Input Matrix (3x3):
-2  -3   3
-5 -10   1
10  30  -5

Output: Minimum Points Required: 7

อัลกอริทึม Dynamic Programming (Bottom-up จากจุดหมาย)

ฟังก์ชัน minInitTokens(matrix)

แนวคิด: คำนวณย้อนกลับจากจุดหมาย

minToken[i][j] = โทเคนขั้นต่ำที่ต้องมี ก่อนเข้า เซลล์ (i,j) เพื่อให้เดินทางต่อไปจนถึงจุดหมายสำเร็จ

ขั้นตอน:

1. Base Case - จุดหมาย (m-1, n-1):
   • ถ้า matrix[m-1][n-1] > 0 → minToken = 1 (ต้องมีอย่างน้อย 1)
   • ถ้า ≤ 0 → minToken = 1 + |matrix[m-1][n-1]|
2. เติมคอลัมน์สุดท้าย (ขึ้นบน):
   • minToken[i][n-1] = max(1, minToken[i+1][n-1] - matrix[i][n-1])
3. เติมแถวสุดท้าย (ซ้าย):
   • minToken[m-1][j] = max(1, minToken[m-1][j+1] - matrix[m-1][j])
4. เติมส่วนที่เหลือ (มุมซ้ายบน):
   • rem = min(minToken[i+1][j], minToken[i][j+1]) (เลือกทางที่ต้องการโทเคนน้อยกว่า)
   • minToken[i][j] = max(1, rem - matrix[i][j])
5. คำตอบ = minToken[0][0]

ตัวอย่างโค้ด C++

#include <iostream>
#include <cmath>
#include <algorithm>
#define ROW 3
#define COL 3
using namespace std;

int tokens[ROW][COL] = {
    {-2, -3,  3},
    {-5, -10, 1},
    {10, 30, -5}
};

int minInitPoints() {
    int minToken[ROW][COL];
    int m = ROW, n = COL;

    // จุดหมาย
    minToken[m-1][n-1] = (tokens[m-1][n-1] > 0) ? 1 : abs(tokens[m-1][n-1]) + 1;

    // คอลัมน์สุดท้าย
    for (int i = m-2; i >= 0; i--)
        minToken[i][n-1] = max(minToken[i+1][n-1] - tokens[i][n-1], 1);

    // แถวสุดท้าย
    for (int j = n-2; j >= 0; j--)
        minToken[m-1][j] = max(minToken[m-1][j+1] - tokens[m-1][j], 1);

    // ส่วนกลาง
    for (int i = m-2; i >= 0; i--) {
        for (int j = n-2; j >= 0; j--) {
            int remPoint = min(minToken[i+1][j], minToken[i][j+1]);
            minToken[i][j] = max(remPoint - tokens[i][j], 1);
        }
    }
    return minToken[0][0];
}

int main() {
    cout << "Minimum Points Required: " << minInitPoints();
    return 0;
}

Output

Minimum Points Required: 7

ความซับซ้อน

• Time: O(m × n)
• Space: O(m × n)

การวิเคราะห์ตัวอย่าง

เส้นทางที่ดีที่สุด: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)

เริ่มต้น 7 → -2 → 5 → -3 → 2 → +3 → 5 → +1 → 6 → -5 → 1 ✓