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 total cost incurred is minimum.
Answers
Step-by-step explanation:
Given a two dimensional grid, 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 total cost incurred is minimum.
Note : It is assumed that negative cost cycles do not exist in input matrix.
This problem is extension of below problem.
A cost grid is given in below diagram, minimum
cost to reach bottom right from top left
is 327 (= 31 + 10 + 13 + 47 + 65 + 12 + 18 +
6 + 33 + 11 + 20 + 41 + 20)
The chosen least cost path is shown in green.
Answer:
if we can go diaognally, then that would be the cheapest way and if we can't, then the next cheapest way would be going to the top right corner and then the bottom right corner