最小コストパスのためのPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します。

問題の説明 −コストマトリックスと位置（m、n）が与えられているので、（0、0）から（m、n）に到達するための最小コストパスのコストを見つける必要があります。各セルは、あるセルから別のセルに移動するためのコストを表します。

次に、以下の実装のソリューションを見てみましょう-

例

# dynamic approach
R = 3
C = 3
def minCost(cost, m, n):
   # initialization
   tc = [[0 for x in range(C)] for x in range(R)]
   # base case
   tc[0][0] = cost[0][0]
   # total cost(tc) array
   for i in range(1, m + 1):
      tc[i][0] = tc[i-1][0] + cost[i][0]
   # tc array
   for j in range(1, n + 1):
      tc[0][j] = tc[0][j-1] + cost[0][j]
   # rest tc array
   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))

出力

Total Cost: 13

すべての変数はローカルスコープで宣言されており、それらの参照は上の図に示されています。