Dynamic Programming – Distinct Paths between two points

Introduction

This is the second post in Dynamic Programming – Online Classes.

This is another article which demonstrates the usage of dynamic programming to solve a different problem in hand. To learn the basics of dynamic programming check my first article on dynamic programming.

Purpose of the article

The purpose of this article is to solve another problem using dynamic programming, this is another very famous interview question which is asked in multiple interviews. So without wasting any time, let us jump into the problem and ways to solve the same.

Count the number of distinct paths between two points on a two dimensional co-ordinate plain

We are given two points x1, y1 and x2, y2 on a two dimensional co-ordinate plain. The task at hand is to count the number of distinct paths from x1, y1 to x2, y2.
Assumption: x2 is greater than x1 and y2 is greater than y1.
Restriction: We can only move either up or right one step at a time, we cannot trace back or down.

Here is a diagram to explain the problem in more detail:
xytraverse
In the diagram above Point1 has co-ordinates (2,1) and Point2 has co-ordinates (4,2). We are at Point1 and we have to reach Point2. We have to find out the total number of distinct way from Point1 to Point2.

The three paths shown in the diagram are the only possible distinct paths. The three paths are painted in RED , GREEN and PURPLE.

How to mathematically solve it?

I would like to show the mathematical way of finding this, as per the restriction defined above we can move only one step at a time. We have to move two steps (x2 – x1) in the right and one step (y2 – y1) in the up direction.

This is a simple problem of counting where we have two similar steps to be taken one at a time in the right direction and one step in the up direction. This is as good as picking (a + b) objects where a objects are of one type and b object is of second type.

The mathematical formula for this is (a+b)! divided by (a! * b!)
Let us verify the same with our diagram. Total number of distinct steps would be ((4-2) + (2-1))! divided by ((4-2)! * (2-1)!).
This would result into (2+1)! divided by (2! * 1!) which equals to 3! divided by 2 , because [ 2! is 2 and 1! is 1].

So total number of distinct paths would be 3 according to the above calculations. We can find it for any to co-ordinates in the plain.

Recursive Solution

As we are learning this to write a computer program, so most of the time this mathematical approach is not going to help. Moreover if the co-ordinates are 100 units apart, the factorial program can die and we will never come out of the long running loop or recursion (what so ever we are using to find the factorial).

So we need to find a better approach, we will discuss the top down approach first and it involves recursion.
I will try and define the problem into a smaller sub-problem. If we observe closely, then we find that the total number of ways to reach (x,y) is the sum of total number of ways to reach (x-1, y) and (x,y-1).

Let us say that the total number of distinct paths from point P(x1, y1) to point P(i,j) is Pathi,j. Then Pathi,j = Pathi-1,j + Pathi,j-1.
This is a recursive equation with two recursive calls, it is termed as binary recursion.

Analyzing the Recursive approach

We will like to draw the recursion tree for the recursive equation, we will start with the same example where we have Point2 co-ordinates (4,2). We start at the root with value (4,2) and branch into two, in one branch we reduce the x by 1 and in the other we reduce the y by 1. We keep branching until either x or y in the node is not zero.

Below is the resultant tree:
tree2
What is the height of the tree, as we decrease either x or y at each step and that too by one so the complete height will be a sum of x+y. As it is a binary tree then the total number of nodes would be of the order 2x+y.

This sounds exponential, that means the running time would be definitely too big, but again I can’t stop noticing that the repeated sub problems (most of the nodes have the same set of values).

So as discussed in the article dynamic programming. we can use the technique of storing the calculated values in a map and return the values the next time it is being asked for. The technique is called Memoization. In this we create a map and put the calculated values against the input parameters and next time if it is required we just return it after performing a constant time look up from the map.

For e.g. we can store the values calculated for the node (3,1), (2,1) etc.

So here is the program to calculate the same thing using recursion and without memoization. Please notice the order in which the arguments are passed in the program.

If we use memoization then the running time reduces to the total number of unique sub problems or total number of unique nodes in the tree. and that would be x2 * y, basically the product of the values in the root node. In our case that would be 4 * 2 i.e. 8.

Same is the case of the space complexity, it will be used to store the results of all the unique sub problems i.e. x2 * y, basically the product of the values in the root node. In our case that would be 4 * 2 i.e. 8.

Dynamic Programming Solution

As discussed in the previous articles the dynamic programming is a tabular bottom up approach, so we need to draw a table to demonstrate this. We will try to find the total number of distinct paths from P(1,2) to P(7,9). Below is the table fully constructed:
table2
How did we populate this table
Well, as we discussed above the total number of distinct paths to a point P(i, j) is equal to the sum of total number of distinct paths to a point P(i-1,j) and total number of distinct paths to a point P(i,j-1)

Point worth considering is that if we have to move from a point Q(x,y1) to point Q(x, y2) where the x co-ordinate is same, there is only one way of moving and similarly moving from a point Q(x1,y) to point Q(x2, y) where the y co-ordinate is same, there is only one way of moving.

So, this is the base case, which populates the first column and first row of the table the values in the first row would be 1 and the values in the first column is 1 as well.

Now for calculating the value of cell (i,j) just add the values of cell(i-1,j ) and cell(i, j-1).
How to read the table?
To read the table, let us suppose that we are trying to populate the cell where the row value is 3 and the column value is 4 the cell contains the value 6.
The very first co-ordinate in the table which has a cell value 0 is the co-ordinate (1,2), the cell at the intersection of row 3 and column 3 has co-ordinate (3,4). And the value in the cell i.e. 6 is the total number of distinct paths from the first co-ordinate (1,2) to the co-ordinate (3,4).

This says that if we want to move from (1,2) to (3,4) there are 6 distinct ways of doing it. If you see the last cell of the table, it has a value 1716. That means there are 1716 ways of distinct ways of travelling from (1,2) to (7,9).

Here is the code for the same.

You can return any other value depending on where you want to move.

Conclusion

So this is how we calculate the total number of unique paths to reach from a point(x1,y1) to point(x2,y2). This is relatively simple if we can work the same thing out with a pen and paper.

Hope this helps, happy learning. Stay connected and stay Subscribed