Minimum Cost Path

Given a square grid of size N, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which the total cost incurred is minimum.

• It can be solved with Dijkastras as well.
• Dynamic programming
• Recursion

Use dp to avoid recomputation of calculated arrays to reduce time complexity from mn^3 to mn Dijkastras Algo takes Time Complexity: O(V + E * logV), where V is (NM) and E is also (NM)

Q. How is it different from Minimum Spanning Tree? Ans. Just include the nodes that you want to calculate the cost for in your graph and then you can get the minimum cost path.

Dynamic programming

Time Complexity: O(N * M), where N is the number of rows and M is the number of columns
Auxiliary Space: O(1), since no extra space has been taken

# Python3 program for the
# above approach
 
 
def minCost(cost, row, col):
 
	# For 1st column
	for i in range(1, row):
		cost[i][0] += cost[i - 1][0]
 
	# For 1st row
	for j in range(1, col):
		cost[0][j] += cost[0][j - 1]
 
	# For rest of the 2d matrix
	for i in range(1, row):
		for j in range(1, col):
			cost[i][j] += (min(cost[i - 1][j - 1],
							min(cost[i - 1][j],
								cost[i][j - 1])))
 
	# Returning the value in
	# last cell
	return cost[row - 1][col - 1]
 
 
# Driver code
if __name__ == '__main__':
 
	row = 3
	col = 3
 
	cost = [[1, 2, 3],
			[4, 8, 2],
			[1, 5, 3]]
 
	print(minCost(cost, row, col))
 
# This code is contributed by Amit Katiyar