# 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] Let P[x][y] denote the number of paths from  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, f = 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  -> [m][n] problem into  -> [m-1][n] +  -> [m][n-1], now imagine we have a function called UP(int m, int n), it can tell you how many paths from  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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 class Solution { public: int uniquePaths(int m, int n) { if(m <=0 || n <= 0) return 0; return UP(m-1, n-1); } int UP(int m, int n){ //move out of boundary, it's invalid, should not be counted as a path if(m < 0 || n <0) return 0; //Robot hits the boundary, we can guarantee to have one way to reach the destination if(m==0 || n==0) return 1; //We calculate the sum of how many panths from two paths return UP(m-1, n) + UP(m, n-1); } };

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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 class Solution { public: int uniquePaths(int m, int n) { if(m <=0 || n <= 0) return 0; vector> memo(m, vector(n, 0)); return UP(m-1, n-1, memo); } int UP(int m, int n, vector> &memo){ //move out of boundary, it's invalid, should not be counted as a path if(m < 0 || n <0) return 0; //Robot hits the boundary, we can guarantee to have one way to reach the destination if(m==0 || n==0) return 1; if(memo[m][n] > 0) return memo[m][n]; //We calculate the sum of how many panths from two paths return memo[m][n] = UP(m-1, n, memo) + UP(m, n-1, memo); } };

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  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] = 1, DP[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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 class Solution { public: int uniquePaths(int m, int n) { vector> DP(m, vector(n, 0)); for(int i = 0; i< m; i++){ DP[i] = 1; } for(int j = 0; j < n; j++){ DP[j] = 1; } for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ DP[i][j] = DP[i-1][j] + DP[i][j-1]; } } return DP[m-1][n-1]; } };

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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 class Solution { public: int uniquePaths(int m, int n) { if (m > n) return uniquePaths(n, m); vector pre(m, 1); vector cur(m, 1); for (int j = 1; j < n; j++) { for (int i = 1; i < m; i++) cur[i] = cur[i – 1] + pre[i]; swap(pre, cur); } return pre[m – 1]; } };

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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 class Solution { public: int uniquePaths(int m, int n) { if (m > n) return uniquePaths(n, m); vector cur(m, 1); for (int j = 1; j < n; j++) for (int i = 1; i < m; i++) cur[i] += cur[i – 1]; return cur[m – 1]; } };

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…

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 class Solution { public: int uniquePathsWithObstacles(vector>& a) { int row = a.size(), col = a.size(); if(a == 1) return 0; vector> memo(row, vector(col)); return UPO(a, memo, row-1, col-1); } int UPO(vector> &a, vector> &b, int row, int col){ if(row <0 || col < 0) return 0; else if(row == 0 && col == 0) return 1; else if(b[row][col] > 0) return b[row][col]; else{ if(a[row][col] == 1) return 0; b[row][col] = UPO(a, b, row-1, col) + UPO(a, b, row, col – 1); return b[row][col]; } } };

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] and DP[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. For the first loop, we initialize boundary of the column.Here is the solution:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 class Solution { public: int uniquePathsWithObstacles(vector>& obstacleGrid) { int m = obstacleGrid.size(), n = obstacleGrid.size(); vector > dp(m + 1, vector (n + 1, 0)); dp = 1; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (!obstacleGrid[i – 1][j – 1]) dp[i][j] = dp[i – 1][j] + dp[i][j – 1]; return dp[m][n]; } };

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)”

1. […] you can clearly see the redundant calculation. For more details about recursive tree, please see here. For this problem, we create a vector called memo, which has n + 1 slots (n is the number of […]

Like