Problems Involving Grids - 1

Problem statement

We are going to start from the simplest problems based on Grids and move on to more complex grid problems in subsequent lessons. The problem in this lesson tries to solve the following type of question:

Finding Minimum-Cost Path in a 2-D Matrix

The problem statement is:

Given a cost matrix cost[][], where cost[i][j] 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. (Assume that all costs are positive integers)

Solution: Dynamic programming approach

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., (i-1, j) or from one cell to your left, i.e., (i, j-1). 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][j]

We now compute the values of the base cases, the topmost row and the leftmost column. For the topmost row, a cell can be reached only from the cell on the left of it. Assuming zero-based index,

MinCost(0,j) = MinCost(0,j-1) + Cost[0][j]

MinCost(i,0) = MinCost(i-1,0) + Cost[i][0]

i.e., cost of reaching cell (0,j) = Cost of reaching cell (0,j-1) + Cost of visiting cell (0,j) and similarly, cost of reaching cell (i,0) = Cost of reaching cell (i-1,0) + Cost of visiting cell (i,0).

Let’s look a the code now.