Min Cost Path ในเมทริกซ์ (หาเส้นทางค่าใช้จ่ายน้อยที่สุด)

กำหนดเมทริกซ์ค่าใช้จ่าย (cost matrix) และจุดหมายปลายทาง ต้องการหาเส้นทางจาก (0,0) ไปยังจุดหมายที่มีค่าใช้จ่ายรวมน้อยที่สุด

กฎการเดิน: จากเซลล์ (i,j) เดินได้เฉพาะ → ขวา (i,j+1), ล่าง (i+1,j), ล่างขวา (i+1,j+1)

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

Cost Matrix (3x3):
1  2  3
4  8  2
1  5  3

Destination: (2, 2)
Output: Minimum Cost: 8
เส้นทาง: (0,0)→(0,1)→(1,2)→(2,2) = 1+2+2+3 = 8

อัลกอริทึม Dynamic Programming

ฟังก์ชัน minCostPath(destX, destY, cost)

ขั้นตอน:

1. สร้างเมทริกซ์ totalCost ขนาดเท่า cost matrix
2. totalCost[0][0] = cost[0][0]
3. เติมคอลัมน์แรก: totalCost[i][0] = totalCost[i-1][0] + cost[i][0]
4. เติมแถวแรก: totalCost[0][j] = totalCost[0][j-1] + cost[0][j]
5. เติมส่วนที่เหลือ: สำหรับ i=1..destX, j=1..destY:
   • totalCost[i][j] = min(totalCost[i-1][j-1], totalCost[i-1][j], totalCost[i][j-1]) + cost[i][j]
6. คืน totalCost[destX][destY]

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

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

int cost[ROW][COL] = {
    {1, 2, 3},
    {4, 8, 2},
    {1, 5, 3}
};

int min3(int a, int b, int c) {
    return min(a, min(b, c));
}

int minCostPath(int destX, int destY) {
    int totalCost[ROW][COL];
    totalCost[0][0] = cost[0][0];

    for (int i = 1; i <= destX; i++)
        totalCost[i][0] = totalCost[i-1][0] + cost[i][0];

    for (int j = 1; j <= destY; j++)
        totalCost[0][j] = totalCost[0][j-1] + cost[0][j];

    for (int i = 1; i <= destX; i++)
        for (int j = 1; j <= destY; j++)
            totalCost[i][j] = min3(totalCost[i-1][j-1], totalCost[i-1][j], totalCost[i][j-1]) + cost[i][j];

    return totalCost[destX][destY];
}

int main() {
    cout << "Minimum Cost: " << minCostPath(2, 2);
    return 0;
}

Output

Minimum Cost: 8

ความซับซ้อน

• Time: O(destX × destY)
• Space: O(destX × destY) (ลดเป็น O(min(destX, destY)) ได้)

การขยาย: หาเส้นทางจริง (Path Reconstruction)

เก็บทิศทางที่มาจากไหน (diagonal/up/left) ในตารางแยก แล้ว trace back จากจุดหมาย