UniquePaths [source code]
public class UniquePaths {
static
/******************************************************************************/
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = m - 1; i >= 0; i--) for (int j = n - 1; j >= 0; j--) {
if (i == m - 1 || j == n - 1)
dp[i][j] = 1;
else
dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
}
return dp[0][0];
}
}
/******************************************************************************/
public static void main(String[] args) {
UniquePaths.Solution tester = new UniquePaths.Solution();
}
}
unique path的问题好像之前见到过一次, 但是是直接DFS走, 然后用一个set来收集, set里面存放的是sequence of moves(directions)来提高效率;
这题的tag里面有DP, 那么感觉好像有更好的办法?
没错, 这题是可以DP的, 因为这种matrix的问题, DP的时候的一个难点, 就是dependency order问题的解决; 但是这题设定的时候, 故意让你不用担心这个问题: 只能向右或者向下;
那么, 如果没有tag, 那么这题让你想到DP的导火索是什么? 可以说是limited movement in matrix.
轻松愉快的秒杀了, 速度是1ms (5%);
另外, 这题空间占用优化到O(min (m, n))应该是很简单的, 别跟我说你不会;
没有editorial;
@jianchao.li.fighter said in 0ms, 5-lines DP Solution in C++ with Explanations:
This is a fundamental DP problem. First of all, let's make some observations.
Since the robot can only move right and down, when it arrives at a point, there are only two possibilities:
- It arrives at that point from above (moving down to that point);
- It arrives at that point from left (moving right to that point).
Thus, we have the following state equations: suppose the number of paths to arrive at a point
(i, j)is denoted asP[i][j], it is easily concluded thatP[i][j] = P[i - 1][j] + P[i][j - 1].The boundary conditions of the above equation occur at the leftmost column (
P[i][j - 1]does not exist) and the uppermost row (P[i - 1][j]does not exist). These conditions can be handled by initialization (pre-processing) --- initializeP[0][j] = 1, P[i][0] = 1for all validi, j. Note the initial value is1instead of0!Now we can write down the following (unoptimized) code.
class Solution {
int uniquePaths(int m, int n) {
vector<vector<int> > path(m, vector<int> (n, 1));
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
path[i][j] = path[i - 1][j] + path[i][j - 1];
return path[m - 1][n - 1];
}
};
As can be seen, the above solution runs in
O(n^2)time and costsO(m*n)space. However, you may have observed that each time when we updatepath[i][j], we only needpath[i - 1][j](at the same column) andpath[i][j - 1](at the left column). So it is enough to maintain two columns (the current column and the left column) instead of maintaining the fullm*nmatrix. Now the code can be optimized to haveO(min(m, n))space complexity.
class Solution {
int uniquePaths(int m, int n) {
if (m > n) return uniquePaths(n, m);
vector<int> pre(m, 1);
vector<int> 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];
}
};
Further inspecting the above code, we find that keeping two columns is used to recover
pre[i], which is justcur[i]before its update. So there is even no need to use two vectors and one is just enough. Now the space is further saved and the code also gets much shorter.
class Solution {
int uniquePaths(int m, int n) {
if (m > n) return uniquePaths(n, m);
vector<int> 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];
}
};
Well, till now, I guess you may even want to optimize it to
O(1)space complexity since the above code seems to rely on onlycur[i]andcur[i - 1]. You may think that 2 variables is enough? Well, it is not. Since the wholecurneeds to be updated forn - 1times, it means that all of its values need to be saved for next update and so two variables is not enough.
没有仔细看了, 总体来说感觉讲的有点小白;
另外, 其实我感觉他这种从左到右的做法和我的从右到左的做法, declarative的理解上面可能可以稍微有点区别; 从右到左, 实际上就很简单, 简单的利用subproblem组合的思路而已; 而他这个从左到右的思路, 感觉有点像以前学shortest path的算法的时候的思路; 当你想要到达一个终点的时候, 研究的是v的parent能够有什么结果;
@d40a said in My AC solution using formula:
Binomial coefficient:
class Solution {
public:
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;
}
};
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).
点醒了之后还是很好理解的; 这个想法很有意思; 另外, 稍微学习一下他这里算排列组合的方式;
也有人提出了异议:
@carterbao said in My AC solution using formula:
the calculation res = res * (N - k + i) / i; may cause losing precision, and as the number gets larger, the error may increase, how can you guarantee that (int)res is the exact result?
这个确实是一个顾虑; 主要是他每一个iteration乘的是一个float(是一个商), 所以可能会有问题; 那么要么就直接全都用int计算: 直接算N!, 在过程中, k!和(n-k)!都可以顺便被计算出来; 那么OP原来的算法的速度是O(min (m, n))(稍微加一个选最小值的优化: int k = min (m, n) - 1;). 如果为了避免float, 那么最后得到的也无非是O(m + n), 还是可以接受的;
@whitehat said in Math solution, O(1) space:
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!)
Following is my code doing the same :-
public class Solution {
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;
}
}
@i4never said in Math solution, O(1) space:
The answer is correct but I think if m and n become bigger, (m+n)! may exceed the range of int while DP solution is free from this problem :)
想法是好的, 虽然这题实际上告诉了你了m和n不会太大;
另外关于这个人的装逼swap(不使用temp来完成swap实际上是一个考题):
@olaolaola said in Math solution, O(1) space:
@whitehat I think the swap step can be improved. m + n may be larger than Integer.MAX_VALUE. So, it would be better to use bitwise operation to swap.
submission基本波动:
class Solution {
public int uniquePaths(int m, int n) {
int[] row = new int[n];
Arrays.fill(row,1);
for ( int i = 1; i < m; i++){
for ( int j = 1; j < n; j++){
row[j]+=row[j-1];
}
}
return row[n-1];
}
}
就是优化了一下space; java里面因为二维数组实际上是通过object来实现的, 所以可能有一点微小的overhead节省, 不过不是题目的重点;
Problem Description
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 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Difficulty:Medium
Total Accepted:177.2K
Total Submissions:417.5K
Contributor:LeetCode
Companies
bloomberg
Related Topics
arraydynamic programming
Similar Questions
Unique Paths IIMinimum Path SumDungeon Game