Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell. Total cost of a path to reach (m, n) is sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.
For example, in the following figure, what is the minimum cost path to (2, 2)?Â
Â
The path with minimum cost is highlighted in the following figure. The path is (0, 0) –> (0, 1) –> (1, 2) –> (2, 2). The cost of the path is 8 (1 + 2 + 2 + 3).Â
Â
Python
# Dynamic Programming Python implementation of Min Cost Path# problemR = 3C = 3Â
def minCost(cost, m, n):Â
    # Instead of following line, we can use int tc[m + 1][n + 1] or    # dynamically allocate memory to save space. The following    # line is used to keep te program simple and make it working    # on all compilers.    tc = [[0 for x in range(C)] for x in range(R)]Â
    tc[0][0] = cost[0][0]Â
    # Initialize first column of total cost(tc) array    for i in range(1, m + 1):        tc[i][0] = tc[i-1][0] + cost[i][0]Â
    # Initialize first row of tc array    for j in range(1, n + 1):        tc[0][j] = tc[0][j-1] + cost[0][j]Â
    # Construct rest of the 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]Â
# Driver program to test above functionscost = [[1, 2, 3],        [4, 8, 2],        [1, 5, 3]]print(minCost(cost, 2, 2))Â
# This code is contributed by Bhavya Jain |
8
Â
Time Complexity: O(m*n)
Auxiliary Space: O(m*n)
Please refer complete article on Dynamic Programming | Set 6 (Min Cost Path) for more details!
Â
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
