# Solving the Unique Paths Problem using Dynamic Programming

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:

DP refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner:- https://www.wikiwand.com/en/Dynamic_programming

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 **):

move(**currentRow**+1)

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**):

move(**currentColumn**+1)

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