LeetCode 73 - Unique Paths 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). How many possible unique paths are there?
dp[m][n] = dp[m][n-1] + dp[m-1][n] where dp[m][n] denotes the number of unique paths
Backtracking Solution:
Code from http://www.cnblogs.com/TenosDoIt/p/3704091.html
int uniquePaths(int m, int n) {
if(m == 1 || n == 1)return 1;
else return uniquePaths(m, n - 1) + uniquePaths(m - 1, n);
}
Dynamic Programming Solution using Bottom-up Approach:
O(n^2) space & time: Code from http://joycelearning.blogspot.com/2013/10/leetcode-unique-paths.html
O(n^2) time, O(n) space
https://leetcode.com/discuss/17530/java-dp-solution-with-complexity-o-n-m
No matter how you choose your path, they must have exactly (m+n-2) moves containm−1 "down" and n−1 "right". A path is simply a combination you selectm−1 (or n−1 ) moves from them and assign it with "down" (or "right"). As a result, you just need to calculate the number of such combinations.
其实这个和组合数有关，对于m*n的网格，从左上角走到右下角，总共需要走m+n-2步，其中必定有m-1步是朝右走，n-1步是朝下走，那么这个问题的答案就是组合数：
, 这里需要注意的是求组合数时防止乘法溢出
Code from http://www.darrensunny.me/leetcode-unique-paths/
Code from http://www.cnblogs.com/TenosDoIt/p/3704091.html
X. Math
https://leetcode.com/discuss/9110/my-ac-solution-using-formula
int uniquePaths(int m, int n) {
int N = n + m - 2;// how much steps we need to do
int k = m - 1; // number of steps that need to go down
double res = 1;
// here we calculate the total possible path number
// Combination(N, k) = n! / (k!(n - k)!)
// reduce the numerator and denominator and get
// C = ( (n - k + 1) * (n - k + 2) * ... * n ) / k!
for (int i = 1; i <= k; i++)
res = res * (N - k + i) / i;
return (int)res;
}
https://discuss.leetcode.com/topic/19613/math-solution-o-1-space
https://discuss.leetcode.com/topic/31724/java-solution-0ms-4lines
http://bookshadow.com/weblog/2015/10/11/leetcode-unique-paths/
http://agoodcode.blogspot.com/2014/04/leetcode-unique-paths.html
O(min(m,n))
int uniquePaths(int m, int n) {
return combination(m+n-2, m-1);
}
int combination(int a, int b)
{
if(b > (a >> 1))b = a - b;
long long res = 1;
for(int i = 1; i <= b; i++)
res = res * (a - i + 1) / i;
return res;
}
class Solution(object): def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int """ if m < n: m, n = n, m mul = lambda x, y: reduce(operator.mul, range(x, y), 1) return mul(m, m + n - 1) / mul(1, n)
X. DFS
http://www.programcreek.com/2014/05/leetcode-unique-paths-java/
Read full article from Unique Paths | LeetCode
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?
dp[m][n] = dp[m][n-1] + dp[m-1][n] where dp[m][n] denotes the number of unique paths
Backtracking Solution:
Code from http://www.cnblogs.com/TenosDoIt/p/3704091.html
int uniquePaths(int m, int n) {
if(m == 1 || n == 1)return 1;
else return uniquePaths(m, n - 1) + uniquePaths(m - 1, n);
}
Dynamic Programming Solution using Bottom-up Approach:
O(n^2) space & time: Code from http://joycelearning.blogspot.com/2013/10/leetcode-unique-paths.html
public int uniquePaths(int m, int n) { int[][] res = new int[m][n]; // init left for(int i = 0; i < m; i++) { res[i][0] = 1; } // init top for(int j = 0; j < n; j++) { res[0][j] = 1; } // add values for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { res[i][j] = res[i - 1][j] + res[i][j - 1]; } } return res[m - 1][n - 1]; }https://leetcode.com/discuss/17530/java-dp-solution-with-complexity-o-n-m
public int uniquePaths(int m, int n) { if (m == 0 || n == 0) { return 0; } if (m == 1 || n == 1) { return 1; } int[] dp = new int[n]; for (int i = 0; i < n; i++) { dp[i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j - 1]; } } return dp[n - 1]; }
public int uniquePaths(int m, int n) { int[] res = new int[n]; // init array for(int j = 0; j < n; j++) { res[j] = 1; } // add values for(int i = 1; i < m; i++) { // reset the head to 1 (simulate the next row head) // similar to set all left most elements in a 2D array to 1 res[0] = 1; for(int j = 1; j < n; j++) { res[j] = res[j - 1] + res[j]; } } return res[n - 1]; }int uniquePaths(int m, int n) { 4 vector<int>dp(n+1, 1); 5 for(int i = 2; i <= m; i++) 6 for(int j = 2; j <= n; j++) 7 dp[j] = dp[j] + dp[j-1]; 8 return dp[n];9 }
No matter how you choose your path, they must have exactly (m+n-2) moves contain
其实这个和组合数有关，对于m*n的网格，从左上角走到右下角，总共需要走m+n-2步，其中必定有m-1步是朝右走，n-1步是朝下走，那么这个问题的答案就是组合数：
, 这里需要注意的是求组合数时防止乘法溢出 Code from http://www.darrensunny.me/leetcode-unique-paths/
public int uniquePaths(int m, int n) {
// Formulation: find the number of combinations when picking m-1 (or n-1) items
// from m+n-2 different items, which is (m+n-2)! / ((m-1)!(n-1)!)
// = m(m+1)...(m+n-2) / (n-1)! (for ease of computation, if m is larger)
int smaller, larger;
if (m < n) {
smaller = m-1;
larger = n-1;
} else {
smaller = n-1;
larger = m-1;
}
long denom = 1, numer = 1; // Use "long" in case of overflow
for (int i = 1; i <= smaller; i++) {
denom *= i;
numer *= larger+i;
}
return (int)(numer/denom);
}
Code from http://www.cnblogs.com/TenosDoIt/p/3704091.html
X. Math
https://leetcode.com/discuss/9110/my-ac-solution-using-formula
First of all you should understand that we need to do n + m - 2 movements : m - 1 down, n - 1 right, because we start from cell (1, 1).
Secondly, the path it is the sequence of movements( go down / go right), therefore we can say that two paths are different when there is i-th (1 .. m + n - 2) movement in path1 differ i-th movement in path2.
So, how we can build paths. Let's choose (n - 1) movements(number of steps to the right) from (m + n - 2), and rest (m - 1) is (number of steps down).
I think now it is obvious that count of different paths are all combinations (n - 1) movements from (m + n-2).
https://discuss.leetcode.com/topic/19613/math-solution-o-1-space
https://discuss.leetcode.com/topic/31724/java-solution-0ms-4lines
This is a combinatorial problem and can be solved without DP. For mxn grid, robot has to move exactly m-1 steps down and n-1 steps right and these can be done in any order.
For the eg., given in question, 3x7 matrix, robot needs to take 2+6 = 8 steps with 2 down and 6 right in any order. That is nothing but a permutation problem. Denote down as 'D' and right as 'R', following is one of the path :-
D R R R D R R R
We have to tell the total number of permutations of the above given word. So, decrease both m & n by 1 and apply following formula:-
Total permutations = (m+n)! / (m! * n!)
public int uniquePaths(int m, int n) {
if(m == 1 || n == 1)
return 1;
m--;
n--;
if(m < n) { // Swap, so that m is the bigger number
m = m + n;
n = m - n;
m = m - n;
}
long res = 1;
int j = 1;
for(int i = m+1; i <= m+n; i++, j++){ // Instead of taking factorial, keep on multiply & divide
res *= i;
res /= j;
}
return (int)res;
}http://bookshadow.com/weblog/2015/10/11/leetcode-unique-paths/
题目可以转化为下面的问题：
求m - 1个白球，n - 1个黑球的排列方式
(m+n-2)!/(m-1)!(n-1)!http://agoodcode.blogspot.com/2014/04/leetcode-unique-paths.html
O(min(m,n))
int uniquePaths(int m, int n) {
return combination(m+n-2, m-1);
}
int combination(int a, int b)
{
if(b > (a >> 1))b = a - b;
long long res = 1;
for(int i = 1; i <= b; i++)
res = res * (a - i + 1) / i;
return res;
}
class Solution(object): def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int """ if m < n: m, n = n, m mul = lambda x, y: reduce(operator.mul, range(x, y), 1) return mul(m, m + n - 1) / mul(1, n)
X. DFS
http://www.programcreek.com/2014/05/leetcode-unique-paths-java/
Read full article from Unique Paths | LeetCode
