A robot is located at the top-left corner of a

mxngrid (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?

This question appears originally from Google Treasure Hunt. This problem is interesting because it can be solved using multiple approaches.

**Hint:** Try to use the most direct way to solve it, and see if you can improve the efficiency.

**Backtracking Solution:**

The most direct way is to** **write code that traverses each possible path, which can be done using backtracking. When you reach row=*m* and col=*n*, you know you’ve reached the bottom-right corner, and there is one additional unique path to it. However, when you reach row>*m* or col>*n*, then it’s an invalid path and you should stop traversing. For any grid at row=*r* and col=*c*, you have two choices: Traverse to the right or traverse to the bottom. Therefore, the total unique paths at grid (*r*,*c*) is equal to the sum of total unique paths from the grid to the right and the grid below. Below is the backtracking code in 5 lines of code:

1 2 3 4 5 6 7 8 |
int backtrack(int r, int c, int m, int n) { if (r == m && c == n) return 1; if (r > m || c > n) return 0; return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n); } |

**Improved Backtracking Solution using Memoization:**

Although the above backtracking solution is easy to code, it is very inefficient in the sense that it recalculates the same solution for a grid over and over again. By caching the results, we prevent recalculation and only calculates when necessary. Here, we are using a dynamic programming (DP) technique called memoization.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
const int M_MAX = 100; const int N_MAX = 100; int backtrack(int r, int c, int m, int n, int mat[][N_MAX+2]) { if (r == m && c == n) return 1; if (r > m || c > n) return 0; if (mat[r+1][c] == -1) mat[r+1][c] = backtrack(r+1, c, m, n, mat); if (mat[r][c+1] == -1) mat[r][c+1] = backtrack(r, c+1, m, n, mat); return mat[r+1][c] + mat[r][c+1]; } int bt(int m, int n) { int mat[M_MAX+2][N_MAX+2]; for (int i = 0; i < M_MAX+2; i++) { for (int j = 0; j < N_MAX+2; j++) { mat[i][j] = -1; } } return backtrack(1, 1, m, n, mat); } |

**Dynamic Programming Solution using Bottom-up Approach:**

If you notice closely, the above DP solution is using a top-down approach. Now let’s try a bottom-up approach. Remember this important relationship that is necessary for this DP solution to work:

*r*,

*c*) is equal to the sum of total unique paths from grid to the right (

*r*,

*c*+1) and the grid below (

*r*+1,

*c*).

How can this relationship help us solve the problem? We observe that all grids of the bottom edge and right edge must all have only one unique path to the bottom-right corner. Using this as the base case, we can build our way up to our solution at grid (1,1) using the relationship above.

*r*,

*c*) is equal to the sum of total unique paths from grid to the right (

*r*,

*c*+1) and the grid below (

*r*+1,

*c*).

1 2 3 4 5 6 7 8 9 10 11 12 13 |
const int M_MAX = 100; const int N_MAX = 100; int dp(int m, int n) { int mat[M_MAX+2][N_MAX+2] = {0}; mat[m][n+1] = 1; for (int r = m; r >= 1; r--) for (int c = n; c >= 1; c--) mat[r][c] = mat[r+1][c] + mat[r][c+1]; return mat[1][1]; } |

**Combinatorial Solution:**

It turns out this problem could be solved using combinatorics, which no doubt would be the most efficient solution. In order to see it as a combinatorial problem, there are some necessary observations. Look at the 7×3 sample grid in the picture above. Notice that no matter how you traverse the grids, you always traverse a total of 8 steps. To be more exact, you always have to choose 6 steps to the right (**R**) and 2 steps to the bottom (**B**). Therefore, the problem can be transformed to a question of how many ways can you choose 6**R**‘s and 2**B**‘s in these 8 steps. The answer is **C**(8,2) (or **C**(8,6)). Therefore, the general solution for a *m* x* n* grid is **C**(*m*+*n*-2, *m*-1).

**Further Thoughts:**

Now consider if some obstacles are added to the grids marked as ‘X’. How many unique paths would there be? A combinatorial solution is difficult to obtain (I don’t know myself, quite frankly), but the DP solution can be modified easily to accommodate this constraint.

Unique Paths,
your Ad is sort of too much.

0Thanks for your comment. I will consider it seriously.

-1The "mat[m][n+1] = 1;" in bottom up DP solution is a good trick to avoid special treatment in the for loop, good job!

One suggestion: if we are using C/C++/Java etc., I'd rather to put first grid in [0,0] instead of [1,1] to save a little bit space, no big deal though.

0Coding the lazy way is the way to go 🙂

Yeah, I tried to use [0,0] but I think clarity is more important, so I decided on [1,1].

0this one actually reminds me a question – find if a string is interleaved by two other strings. 小尾羊from the mitbbs mentioned this could be done with d.p. Do you have time to elaborate it? Thanks!

0Couldn't the 1st backtrack code be reduced to only 3 lines like:

if (r == m || c == n)

return 1;

return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n);

0@Yuan Jin:

I think I know which question you are talking about. Just to be sure, could you elaborate the question more? A link to the question would be helpful too.

0@Anonymous:

Hmm… You might get the correct solution due to the edge row and columns on the bottom and the right has always exactly one way to reach the corner.

However, if I change the question to add some obstacles to one of the grid in the edge column, your solution would no longer work, since your backtrack code did not traverse all the way to the corner of the grid.

+1"Design an algorithm to find whether a given string is formed by the interleaving of two given strings or not. e.g. s1= aabccabc s2= dbbabc s3= aabdbbccababcc Given s1,s2,s3 design an efficient algorithm to find whether s3 is formed from the interleaving of s1 and s2."

http://www.careercup.com/question?id=2571

-1Thanks Yuan,

I'll look into the problem next and will post my approach in the future. Stay tuned!

0It is better to put the ads in the sidebar instead of in post, if you still want to keep the ads

0Sorry I messed up the formatting since I am experimenting with ads placement. I fixed it now and hopefully the ads do not interfere the content too much. Thanks for your comment as well, I would consider it.

0How are you assuming the bottom most row has just one choice. Shouldn't it have a choice to go up as well.

For Grid

A B C

D E F

G H I

The path could ADGHEBCFI or ADGHI note that at position H you have two choices either go up or right (assuming the up node is not already visited)

0Never mind my previous comment I see it is a constraint that robot can either move down or right. I was considering a more general case where robot can move in any direction but cannot visit the already visited node.

0hi, what changes do we need to make in the bottom-up approach if the step size was equal to the value of the integer in the original grid?

i.e instead of moving one step right or down , one would move by that many steps as the value of integer in the original grid.

E.g

for the following grid:

2313

1213

1231

3110

the answer is 3

0Actually, us the followling way is simpler.

int walks(int m, int n)

{

if (m==0 || n==0)

return 1;

else

return walks(m-1, n) + walks(m, n-1);

}

0Hi, 1337:

In your 2nd solution (Improved Backtracking Solution using Memoization), can’t understand why bt(int m, int n) calls backtrack(1, 1, m, n, mat), instead of backtrack(0, 0, m, n, mat)? Isn’t the top-left element indexed as (0, 0)?

And, in your 3rd DP solution, why just set “mat[m][n+1] = 1”, and not “mat[m+1][n] = 1”? And, why the return value is mat[1][1], not mat[0][0]?

Thanks,

johny

0Hey i1337,

I couldn’t understand why you don’t use the mat[0][0] at all in ur implementation? Is there a specific reason why you do that?

0Pingback: A Microsoft String Replacement Problem | 口├人人│의 Blog

can you explain the complexity of the backtracking algorithm? I read an interview question asking to compare complexity of all different algorithms. and i understand the DP one is O(m*n)

Thanks!

0“memset(mat, -1, sizeof(mat))” is incorrect since it set EVERY BYTE to be -1, not each integer….

0ahh… you are right, and thanks for pointing this out!

Although memset accepts int as the second parameter, it is converted to an unsigned char, and this value is being used to fill each byte of the memory.

However, the code works and I investigated a little to find out why. -1 is being converted to unsigned char, which is 255. That is, each bit is set to 1 for the entire byte. Therefore, with memset -1, each block of memory are being filled with 1’s. Since two complements of an -1 integer is all 4 bytes being filled with 1’s, it coincidentally becomes the value of -1 again, which explains why the above code works.

Even though the code works, it is not my original intention. Thanks and I have modified the code to initialize the array using for loops.

0hey..Why this +2 is added in dp bottom up solution.

“int mat[M_MAX+2][N_MAX+2] = {0};”

i did not get it. can you pl. explain this.

thnx

0I don’t get it either 🙁

0Thnx for a nice explanation….

0Hi i337, Is there a way to print all path AND use DP? It seems like by using DP, a node will be only traversed once. But if all path need to be printed, then some nodes will be traversed more than once, in order to reach the destination again and again, and get printed out. For example, in my code, if you don’t comment out DP, then only 1 path will be printed.

0Awesome website. I learned a lot in this forum.

And just my two cents, to further simplify the code a little bit.

There is no need to allocate a two dimensional array. We can reuse one array for a single row:

int dp(int m, int n) {

int paths[m]; // variable-sized array, allocated in stack.

memset(paths, 0, sizeof(paths));

paths[0] = 1;

for (int i = 0; i < n; i++) {

for (int j = 1; j < m; j++) {

paths[j] += paths[j – 1];

}

}

return paths[m – 1];

}

0Well explained and nice job!

0Very good post.

Two minor things.

1) the testing

may not be necessary in this scenario (as mentioned by Anonymous in Nov 14th);

2) the code for top-down DP approach can be simplified as follows

0If the max of m and n is 100, it should be use double instead of int. (from my test, when m=n=99, C(98, 198) = 5.7165924488905366E57 ).

And to avoid the multiplication and division on the big data, we can store and data as factor list, example: < 2, < >, < 6, <, >, < 100, <, >

+10Could I simply say it is C_(m+n-2){m-1} (Choose m-1 out of m+n-2)? The robot needs to move n-1 steps rightward, and m-1 steps downward, so the total number of unique paths is choosing m-1 (or n-1) out from (m-1+n-1).

+1public class Solution {

public int uniquePaths(int m, int n) {

if (m == 1 || n == 1) return 1;

double count = 1;

for (int k = 0 ; k < n-1 ; k++){

count *= (double)(m+n-2-k) / (double)(n-1-k);

}

return (int) (count+0.5);

}

}

0I also used the same idea, since it more looks like a math problem to me. The only difference is that, I think you can use the BigInteger class to replace “double”, and hence guarantee the correctness in more general cases (when m and n are greater than 100).

0We can calculate it using binomial koefficient.

we have (m-1) + (n – 1) total steps. And only Math.min(m, n) – 1 possible turns.

So if m > n result is (m + n – 2)!/((n – 1)!(m – 2)!)

if m = 7 and n = 3 as in the example:

8!/(2!*6!) = 28

+2Calculate the combination number directly.

0Pingback: LeetCode: Unique Paths | Jerry's Blog

public static int uniquePaths(int[][] matrix, int sx, int sy, int ex, int ey) {

if (matrix == null) {

return 0;

}

// set the row sx to 1

for (int i = sx + 1; i <= ex; i++) {

matrix[i][sy] = 1;

}

for (int i = sy + 1; i <= ey; i++) {

matrix[sx][i] = 1;

}

for (int i = sx + 1; i <= ex; i++) {

for (int j = sy + 1; j <= ey; j++) {

matrix[i][j] = matrix[i – 1][j] + matrix[i][j – 1];

}

}

return matrix[ex][ey];

}

00In the case of combinatoric method, compiler is unable to deal with factorial of a big number (e.g. 100). what should I do ???

0I can not agree with the following statement: “Although the above backtracking solution is easy to code, it is very inefficient in the sense that it recalculates the same solution for a grid over and over again. ” .

The proposed backtracking solution does not recalculate the same solution/path, in fact it never traverses through the same path. The problem about proposed solution is that by traversing one path, it reaches another path, and then it traverses though the reached path again to reach the final node (instead of using the “concatenation”. )

e.g. in grid 3×3, the first backtracking path is reached by RIGHT->RIGHT->DOWN->DOWN. In further iteration, when we are placed in RIGHT->RIGHT->DOWN, the path goes to ->RIGHT (which is the first path). So second path reaches the first, and instead of returning +1 as solution, we are traversing again to the final destination.

0