How to solve Unique path problem

Dynamic programming approach.

Before getting started, let’s discuss about the problem. 

A robot is located at the top-left corner of a grid (m*n) (marked ‘Start’ in the diagram below).

The robot can only move either down or right each time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Understand the problem: 

The problem asks for how many unique paths start from top-left of the grid to the bottom-right.

Now let’s take a scenario. Suppose a 3*2 grid is given. From the top-left corner, our target is to reach the bottom-right corner.

So based on the condition lets see what we can generate.

Path-1: Right → Right → Down
Path-2: Right → Down → Right
Path-3: Down → Right → Right

Hold it right there. That is the solution to this scenario. There are three unique paths. The approach we tried is not Dynamic Programming. Now a fancy word has arrived. what is it? Let’s see…

Dynamic Programming:

(DP) is a technique in computer programming that helps to efficiently solve a class of problems that have overlapping sub-problems and optimal substructure property.

Such problems involve repeatedly calculating the value of the same sub-problems to find the optimum solution.

Let’s take the factorial problem as an example. In mathematics, the factorial of a positive integer n, denoted by n!. Which is the multiplication of all positive integers less than or equal to n.

For example,

5! = 5*4*3*2*1 = 120

Now the parameter of our function to find the factorial is 6. So our factorial function will execute again as,

6! = 6*5*4*3*2*1 = 720

we can divide this factorial of 6 in some sub-problem.

6! = 6* 5!

So if we save the 5! in a position then the calculation of 6! will be easy for us. All we need to multiply the number with its previous calculated factorial. As a result, we are reducing the number of operations. This is the base of dynamic programming.

Now let’s head to our problem. If we try to visualize all the ways that will be tough. So our first task is to divide the problem into sub-problems. Instead of the goal, assume our finish point is the right adjacent square. There is only one way to go there, just have to move right, Same way for the cell below the start, Have to move down. What about diagonal square? well, we have two ways.

1. From start to right, then down
2. From start to down, then right

How can we calculate it in numbers? Aa..ha. That relies on those two steps. If we store the number of ways to move adjacent right and down from the start point, all we need to do is add those two ways for the diagonal one.

Let’s expand our view now if we have a grid of size m*n. what is the number of ways to reach the right squares from the start. It should be 1 because we are not changing our direction, same for the below squares of the start point.

The first row will be filled with 1 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. We need two loops to iterate through each square. which will fill them with the sum of its top square value and left square value. The final result will be stored in the bottom-right corner.

Now finally we got four steps to complete the problem.

1. Fill the first row with 1
2. Fill the first column with 1
3. Fill the rest of the squares with the sum of its top square value and left square value.
4. Return the bottom- right corner square value.

Assume we have a grid 4*3.

First things first, let’s make a matrix dp of 4*3 size. and fill the first row and column with 1.

The second columns first empty place will be filled with its top and left square’s sum. If the place is dp[i][j], then it will be filled with dp[i-1][j]+dp[i][j-1]

we will fill the rest of the empty places of the second row by following the same process.

same goes for the last row

Our final result will be stored at the bottom right corner square, which is

dp[i][j] = dp[i-1][j] + dp[i]dp[j-1]
dp[3][4] = dp[2][4]+dp[3][3]
dp[3][4] = 4 + 6 = 10

So, the ruby approach to solve this problem should be like this

def unique_paths(m, n)
  0 if m == 0 || n == 0
  dp = Array.new(n) { Array.new(m,0) }
  for i in 0...n
    dp[i][0] = 1
  end
  for j in 0...m
    dp[0][j] = 1
  end
  for i in 1...n
    for j in 1...m
      dp[i][j] = dp[i-1][j] + dp[i][j-1]
    end
    print dp
  end
  dp[n-1][m-1]
end

Time Complexity

The time complexity of this algorithm is O(m*n). As the iteration goes for the full size of the grid.

Space Complexity

The main factor of this algorithm is the 2D Array. And its size is dependent on its row and column. So the space complexity for this algorithm is O(m*n) as well.

For further information:

https://www.geeksforgeeks.org/dynamic-programming/

https://leetcode.com/problems/unique-paths/