Chương trình Python Min Cost Path (Đường đi chi phí nhỏ nhất)

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho ma trận chi phí và vị trí (m, n), cần tìm chi phí đường đi nhỏ nhất từ (0, 0) đến (m, n). Mỗi ô chi phí đi từ ô này sang ô khác.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

# quy hoạch động
R = 3
C = 3
def minCost(cost, m, n):
    # khởi tạo
    tc = [[0 for x in range(C)] for x in range(R)]
    # base case
    tc[0][0] = cost[0][0]
    # cột đầu
    for i in range(1, m + 1):
        tc[i][0] = tc[i-1][0] + cost[i][0]
    # hàng đầu
    for j in range(1, n + 1):
        tc[0][j] = tc[0][j-1] + cost[0][j]
    # phần còn lại
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j]
    return tc[m][n]

# main
cost = [[1, 5, 3],
        [7, 7, 4],
        [8, 5, 3]]
print("Tổng chi phí:", minCost(cost, 2, 1))

Kết quả

Tổng chi phí: 13

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python Min Cost Path.