最小成本路径的 Python 程序

pythonserver side programmingprogramming

在本文中，我们将了解下面给出的问题陈述的解决方案。

问题陈述 − 给定一个成本矩阵和一个位置 (m, n)，我们需要找到从 (0, 0) 到达 (m, n) 的最低成本路径的成本。每个单元格代表从一个单元格到另一个单元格的移动成本。

现在让我们观察下面实现中的解决方案 −

示例

# 动态方法
R = 3
C = 3
def minCost(cost, m, n):
   # 初始化
   tc = [[0 for x in range(C)] for x in range(R)]
   # 基本情况
   tc[0][0] = cost[0][0]
   # 总 cost(tc) 数组
   for i in range(1, m + 1):
      tc[i][0] = tc[i-1][0] + cost[i][0]
   # tc 数组
   for j in range(1, n + 1):
      tc[0][j] = tc[0][j-1] + cost[0][j]
   # 其余 tc 数组
   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("Total Cost:",minCost(cost, 2, 1))