Unique Path I && II (Recursion and Dynamic Programming)

Problem Statement:

Unique Path I

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

The robot can only move either down or right at any point in 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?


Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

Solution One – Recursion:

This is a typical problem related to recursion. Since we want to know how many paths can we generate from [0, 0] to [x, y], if we already know the number of paths to get to [x-1, y-1] from [0, 0],  we need to add the number of paths from [x-1] [y-1] to [x][y]. So, how many of paths can we get from [x-1][y-1] to [x][y]? it’s 2:

[x-1][y-1] -> [x-1][y] -> [x][y]

[x-1][y-1] -> [x][y-1] -> [x][y]

TIM截图20181223192703

Let P[x][y] denote the number of paths from [0][0] to [x][y], than we can easily write the formula about how to compute P[x][y]:

P[x][y] = P[x-1][y] + P[x][y-1]; (from both left and up, since robot can only move right or down)(x <= m; y <= n)

You may notice this equation is really like Fibonacci formula, we know that Fibonacci has its base case f[0] = 0, f[1] = 1. Then, what is the base case for this problem?

The base case should be x or y touches the boundary.  Why? Look at the picture below, we can see whenever robot touches the boundary, for the rest of the movement, we have exactly one solution, either go straight down or go straight right:

TIM截图20181223192748

OK, we already know how to divide the [0][0] -> [m][n] problem into [0][0] -> [m-1][n] + [0][0] -> [m][n-1], now imagine we have a function called UP(int m, int n), it can tell you how many paths from [0][0] to [m][n], then we can easily write our code like this:

result[m][n] = UP(m-1, n) + UP(m, n-1);

In this UP(int m, int n) function, we need to check the base case, and provide the exit for the recursive function call.

Let’s wrap up everything and go to the code:

The code is simple and straightforward, however, the time complexity is a little bit tricky. Imagine that we are running this problem, let’s say m = 4, n = 3, you can easily draw the recursive tree like this:

TIM截图20181223203715

In this partially recursive tree, you can see that our code generally generates a binary tree (not balanced), so the number of leave nodes (marked with double black line) are number of valid paths. The depth of the tree depends on the m or n (the bigger one). The time complexity should be exponential because each time when we go to a further layer, we have two branches. This code is too slow.

Time Complexity: ~O( 2^ max(m, n))

Space Complexity: ~O(max(m, n))


Solution Two – Memorization:

This idea is based on the recursive version. If we take a close look at the recursive tree, we can see we did a lot of repetitive computation. Look at the nodes which are marked with green and orange. If we calculate them once, we can save them for later use. This is a typical trick we perform to trade space for time.

TIM截图20181223203715

Then how can we do that?  we allocate a two-dimensional array (m*n) to store all the possible outcomes. When we call our recursive function, we first check whether we have already computed the value, if it is true, we return that value. Here is the code:

Time Complexity: O(m*n)

Space Complexity: O(m*n)


Solution Three – Dynamic Programming:

If we can write our memorization solution, the DP solution should be easy. For most of the DP problem, the hardest part is to define sub problems. As long as you can find the sub problems, the solution should be pretty natural. We highly recommend novice starts from recursion and optimizes to DP solution.

The general concept of DP solution is similar to the memorization problem. We allocate two-dimensional array DP[i][j] to store all the possible outcomes. DP[i][j] means the number of all the unique path from [0][0] to [i][j]. We can reuse the equation here:

DP[i][j] = DP[i-1][j] + DP[i][j-1];

So when we get the array, the rest of the thing we need to do is to filled in the array with outcomes. OK, one thing we need to take care is the base case: what will be the base case?

DP[i][0] = 1, DP[0][j] = 1;

Right? When the robot reaches the boundaries, we can safely say we have found one valid path. Based on the idea, here is the code:

Time Complexity: O(m*n)

Space Complexity: O(m*n)


Solution Three – Optimized DP:

If we take a close look at the code above, we can see that we do not really need m*n space. The reason is simple, because when we update the DP[i][j], we just need DP[i-1][j] and DP[i][j-1]. Then we can only allocate two arrays to store both these values.

The code comes here:

Time Complexity: O(m*n)

Space Complexity: O(m)

Actually, we can even do better. If we take a close look at the code, pre[i] basically is the same as the cur[i] before it updates itself. Then we only need one array instead of two:



Unique Path II

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

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

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Solution One – Memorization:

In general, this is the same problem. We only need to modify several lines of code, then we can get the solution. The idea is that before we update the memo[i][j], we check the values from the original matrix, if we found this path lies on the obstacle, we manually return 0, indicating this path is not valid. The rest is the same…

Time Complexity: O(m*n)

Space Complexity: O(m*n)


Solution One – DP:

As for the DP solution, there is a trick related to the initialization. In the Unique Path I problem, we initialize DP[i][0] and DP[0][j] to all 1s. In this case, due to the obstacle, we have to initialize the boundary according to the obstacles. For example, if obstacleGrid is like [0, 0, 1, 0, 0], then the last three points are not reachable and need to be initialized to be 0. The result is [1, 1, 0, 0, 0]. We add one more row and column, and initialize all the matrix to 0s. Then we set DP[1][0] = 1. For the first loop, we initialize boundary of the column.Here is the solution:

Time Complexity: O(m*n)

Space Complexity: O(m*n)

We can also optimize the space complexity for this problem, just like before… Maybe you can do it yourself?


That’s all for today, thanks for reading…

1 thought on “Unique Path I && II (Recursion and Dynamic Programming)”

Leave a Reply to Word Break I && II – Jun Zhang Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s