Đường đi chi phí tối thiểu trong ma trận (Min Cost Path)

Cho ma trận chi phí, từ ô (0,0) đến ô đích (destX, destY). Chỉ được đi sang phải, xuống dưới, hoặc chéo xuống phải. Tìm đường đi có tổng chi phí nhỏ nhất.

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

Đầu vào: Ma trận 3x3:
1 2 3
4 8 2
1 5 3
Đích: (2,2)

Đầu ra: Minimum Cost = 8
(Đường đi: 1→2→2→3 hoặc 1→4→1→5→3...)

Thuật toán

Bảng totalCost[i][j] = chi phí tối thiểu từ (0,0) đến (i,j).

1. totalCost[0][0] = cost[0][0].
2. Khởi tạo hàng 0 và cột 0 (chỉ có 1 đường đi).
3. Với i,j ≥ 1: totalCost[i][j] = min(totalCost[i-1][j-1], totalCost[i-1][j], totalCost[i][j-1]) + cost[i][j].
4. Trả về totalCost[destX][destY].

Ví dụ C++

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

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

int min(int a, int b, int c) {
    return (a<b)?((a<c)?a:c):((b<c)?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] = min(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);
}

Kết quả

Minimum Cost: 8