Algorithm for Unique Paths problem using Dynamic Programming


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

What is Unique Paths Problem?

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!

Some examples:

Example 1:
Input: m = 3, n = 2
Output: 3
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
Example 2:
Input: m = 7, n = 3
Output: 28

The Unique Paths problem using Dynamic Programming

Intial takes on the question:

  • 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:

The Unique Paths problem using Dynamic Programming
  • 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)
The Unique Paths problem using Dynamic Programming

So do you see it? [i,j] = [i-1,j] + [i, j-1] is the relation we wanted, the relation we were using!

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!


def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int we are at 0,0 at each point we can make two choices, either come from top or come from left """ # To store the results and use them again to prevent re computations. dp = [[1 for i in range(n)] for i in range(m)] # Building up the table as discussed above. for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[-1][-1]

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!

def uniquePaths(self, m, n): if not m or not n: return 0 cur = [1] * n for i in xrange(1, m): for j in xrange(1, n): cur[j] += cur[j - 1] return cur[-1]
        


Comments



Contact Us
Need any Technical Help Online
Message Us
Search

Play 2048 Game Online


Search Tags

    Unique Path Problem Simple Explanation

    Python Code for Unique Path Problem