You are located at a given point of a grid (m*n) , and you need to reach the bottom-right corner of the grid. Let us choose point (1*1) of the grid as the starting point:
You are at position 1 ( 1*1) and you need to move to position marked STOP
Question: How many possible paths can you take to get to your destination? ( Note: You can only move RIGHT or DOWN from any given point)
Before we write our program, let us visualize the solution on the grid.
Fill all the cells of the first row and the first column with 1s because there is only one way to reach every square. same for the first column.
Now we have to fill the rest of the squares. Fill them with the sum of its top square value and left square value.
Now let us write a program that can compute the possible paths for us using Dynamic Programming.
Before going any further, let us understand what DP means:
Each of those sub-problems are solved just once, and storing their solutions which are then used to find the solution to the main problem.
Now let us see how we can use DP to solve our above problem:
Our smallest sub-problem here is a 2*2 grid:
Let us name our starting point as currentRow = 1, currentColumn = 1. We will know we have arrived at our destination when our currentRow == gridRows and currentColumn== gridColumns. This forms our base case for our DP approach
if currentColumn==gridColumns and currentRow==gridRows: return 1
We solve our sub-problem by either moving one step right, or one step down. Incrementing currentColumn by 1 moves us one step to the right, while incrementing currentRow by 1 moves us one step down.
move(currentColumn+1) or move(currentRow+1)
# if the currentColumn is equal to the total grid columns and the currentRow value is less than the total grid rows, then we know we have reached the furthest column, and therefore we should move down
if(currentColumn == gridColumns and currentRow < gridRows ):
If the currentRow value is equal to the grid rows and the currentColumn value is less than the grid columns, then we know we have reached the lowest row, and therefore we should move right
if(currentRow== gridRows and currentColumn< gridColumns):
Since we know we have reached our destination when currentRow== gridRows and currentColumn== gridColumns and a value 1 is returned,
all we now need to do is to add the result from the right move to the down move
move(currentRow+1) + move(currentColumn+1)
And below is our complete function written in python:
Calling the function:
move(1,1,6,5) # returns 126 for a 6*5 grid
move(1,1,2,2) # returns 2 for a 2*2 grid