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

Problem Statement:

Unique Path I

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

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]

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:

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:

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.

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

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…