In this article, we will cover a famous dynamic programming question, "Unique paths".

This is the second part of the Dynamic Programming Series. (1B) Each category comprises of 4-5 questions.

We will be covering 4 major categories

This is category A: Finding Distinct Ways

Question No 2: Unique paths

Consider a robot/person that has to reach from a starting point to a final location in a 2D grid with m rows and n columns

The person to start with is on the top left position (0,0) and it has to reach the last cell, the bottom right corner (m-1, n-1)

Our person can only move DOWN OR RIGHT AT ANY POINT IN TIME, It has only these two choice

Now it is sure that the guy can reach the end, but how many unique paths are there? This is what we need to compute!

In above example, I can come following any one of these 3 paths, these are the only unique paths:

1. Right -> Right -> Down

2. Right -> Down -> Right

3. Down -> Right -> Right

Input: m = 7, n = 3

Output: 28

- We need to reach the bottom right cell of the grid step by step
- We have to make a choice at every step we take, the choices are: Go right or Go down!
- We need to tell that in how many unique (distinct) ways are there to reach the end point!

Now that we have pretty much understood what the question wants we will now understand how to approach it in a step by step manner

Let's try to break the problem down a bit. Just to make things easier to understand and see if we can form some relation!
So to reach a given cell, I can either come from the cell right above me or the cell that is right to the left of me!

Looking a the diagram it is pretty clear that to reach a cell (i,j), I can either come from the cell (i-1, j) or the cell (i, j-1).

These are all the possibilities! Hence the answer for this cell is nothing but the sum of the possibilities on these two cells! Simple as that!

Now lets go through the example properly to understand how the DP concept will walk into picture!

Say that we have the following example at hand

Remember at each point we can either go right or go down, so lets try to understand it now! Let's look at the possibilities:

- Notice how we will make use of precomputed results
- To reach any point in the first row, we can only go right always, hence to reach any cell in this row there is only and only 1 way!
- Similarly, To reach any point in the first column, we can only go down always, hence to reach any cell in this column there is only and only 1 way!
- Now our real thinking starts, think about the cell at (1,1) we can reach it either from (0,1) or from (1,0) i.e. from the Top or from the Left. Hence we will write here a 1+1 = 2.
- Look one step right now at cell (1,2), I can come here from top (0,2) or from the left (1,1). Now we have a big advantage here! We do not need to recompute the value for the cell (1,1) we have stored it already! Hence in this cell we can fill the sum of values from (0,3) and (1,1) = 1 + 2 = 3

And similarly, we can fill the remaining values, but wait a minute... did you notice some pattern?

To compute value at (1,1) we used--> (1,0) and (0,1)

To compute value at (1,2) we used--> (1,1) and (0,2)

.

.

.

To compute value at (2,6) we will use-->(2,5) and (1,6)

Now simply following the steps discussed above we can write our code, we will be using a 2D array (dp) to store the computations, so that we can use them later!

Also, each time when we put value into dp[i][j], we only need dp[i - 1][j] (previous row) and dp[i][j - 1] (current row), so we can reduce the space needed!

- Mumbai University Computer Engineering Machine Learning (ML) Semester 8 Important Notes Download
- What is Performance Testing and Stress Testing?
- Dijkstra's Algorithm and Flow Chart with Implementation in Java
- How to count the number of words in a sentence using C++
- Steps For Installing Git on Ubuntu 18.04 LTS