Take in the blocked cells and mark them with a special value(-1 here) Note that we'll be using 1-based indexing here. declaring a Grid array which stores the number of paths Take input the number of rows, columns and blocked cells Calculate number of ways visiting (i,j) using the Initialize first column of NumWays Matrix initialize first row of NumWays matrix Calculate cost of visiting (i,j) using the This bottom-up approach ensures that all the sub-problems needed Initialize first column of MinCost Matrix initialize first row of MinCost matrix Take input the cost of visiting cell (i,j) Int X,Y //X:number of rows, Y: number of columns See the code below for more understanding. cost of reaching cell (i,0) = Cost of reaching cell (i-1,0) + Cost of visiting cell (i,0) Similarly, MinCost(i,0) = MinCost(i-1,0) + Cost 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 Finding the number of ways to reach a particular position in a grid from a starting position (given some cells which are blocked)ΔΆ.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |