cost of reaching cell (0,j) = Cost of reaching cell (0,j-1) + Cost of visiting cell (0,j) Assuming zero-based index, MinCost(0,j) = MinCost(0,j-1) + Cost For the topmost row, a cell can be reached only from the cell on the left of it. We now compute the values of the base cases: the topmost row and the leftmost column. The problem of finding the min-Cost Path is now almost solved. (You can google the above two terms for more details) This saves the time needed to compute the same sub-problems again and again. Overlapping Sub-problems:- Subproblems once computed can be stored in a table for further use. Optimal Sub-structure:- Optimal solution to a problem involves optimal solutions to sub-problems. This brings us to the two important conditions which need to be satisfied for a dynamic programming problem:
The above statement means that to reach cell (i,j) wit minimum cost, first reach either cell(i-1,j) or cell (i,j-1) in as minimum cost as possible.
This means that the cost of visiting cell (i,j) will come from the following recurrence relation: MinCost(i,j) = min(MinCost(i-1,j),MinCost(i,j-1)) + Cost (i-1,j) or from one cell to your left, i.e. Solution : It is very easy to note that if you reach a position (i,j) in the grid, you must have come from one cell higher, i.e. (We assume that all costs are positive integers) Problem Statement : Given a cost matrix Cost where Cost denotes the Cost of visiting cell with coordinates (i,j), find a min-cost path to reach a cell (x,y) from cell (0,0) under the condition that you can only travel one step right or one step down. Finding Minimum-Cost Path in a 2-D Matrix
There are many problems in online coding contests which involve finding a minimum-cost path in a grid, finding the number of ways to reach a particular position from a given starting point in a 2-D grid and so on.
0 kommentar(er)
