UniquePathsII [source code]
public class UniquePathsII {
static
/******************************************************************************/
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0)
return 0;
final int R = obstacleGrid.length, C = obstacleGrid[0].length;
int[][] dp = new int[R][C];
for (int i = R - 1; i >= 0; i--) for (int j = C - 1; j >= 0; j--) {
if (obstacleGrid[i][j] == 1)
dp[i][j] = 0;
else if (i == R - 1 && j == C - 1)
dp[i][j] = 1;
else if (i == R - 1)
dp[i][j] = dp[i][j + 1];
else if (j == C - 1)
dp[i][j] = dp[i + 1][j];
else
dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
}
return dp[0][0];
}
}
/******************************************************************************/
public static void main(String[] args) {
UniquePathsII.Solution tester = new UniquePathsII.Solution();
}
}
好像并没有什么卵区别? 直接还是DP继续做就行了;
照样秒杀, 速度是1ms (11%);
没有editorial;
@tusizi said in Short JAVA solution:
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int width = obstacleGrid[0].length;
int[] dp = new int[width];
dp[0] = 1;
for (int[] row : obstacleGrid) {
for (int j = 0; j < width; j++) {
if (row[j] == 1)
dp[j] = 0;
else if (j > 0)
dp[j] += dp[j - 1];
}
}
return dp[width - 1];
}
就是空间优化之后的DP; 本来以为这个空间优化很trivial, 没想到这个算法其实还看了小半天才彻底搞懂; 关键还是要理解运算过程;
适当熟悉一下这个算法, 其实1D DP我写的并不多, 如果临时让我写我并没有把我就一定能写的很好;
这题实际上还有O(1)空间的做法, 你猜猜是怎么写的?
其实并不是通过对DP本身的优化, 而是用InPlace的技巧; 反正这个技巧, 如果问道让你O(1)space的时候, 要能想到; 本身并不是一个特别难的东西, 实际上写起来难度比上面那个1D的写法要简单很多, 但是就怕你想不到;
@SpicyDog said in Short JAVA solution:
Without extra space: (I can combine all three loop into one, but I don't wanna have too much condition checking.)
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
//flip upper left cell (the start cell): 1 => 0 or 0 => 1
obstacleGrid[0][0] ^= 1;
//first row: if 1, then 0; otherwise, left cell
for(int i = 1; i < n; i++)
obstacleGrid[0][i] = obstacleGrid[0][i] == 1 ? 0 : obstacleGrid[0][i - 1];
//first column: if 1, then 0; otherwise, top cell
for(int i = 1; i < m; i++)
obstacleGrid[i][0] = obstacleGrid[i][0] == 1 ? 0 : obstacleGrid[i - 1][0];
//rest: if 1, then 0; otherwise, left cell + top cell
for(int i = 1; i < m; i++)
for(int j = 1; j < n; j++)
obstacleGrid[i][j] = obstacleGrid[i][j] == 1 ? 0 : obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
//return lower right cell (the end cell)
return obstacleGrid[m - 1][n - 1];
}
}
@BirdFrank said in Short JAVA solution:
dp[j] += dp[j - 1];isdp[j] = dp[j] + dp[j - 1];which is
new dp[j] = old dp[j] + dp[j-1]
which iscurrent cell = top cell + left cellHope this helps.
@yavinci said in Short JAVA solution:
This is the best solution without modifying original grid.
InPlace换来的O(1) space确实是有一定争议的; 严格来说这种做法其实是steal space;
@kingmacrobo said in My C++ Dp solution , very simple!:
just use dp to find the answer , if there is a obstacle at (i,j), then dp[i][j] = 0.
time is O(nm) , space is O(nm) .
here is my code:
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m = obstacleGrid.size() , n = obstacleGrid[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
dp[0][1] = 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];
}
};
刚开始看不懂, 看懂了之后才发现其实挺无聊的; 虽然底下有人吹:
@jianchao.li.fighter said in My C++ Dp solution , very simple!:
Nice pre-processing
dp[0][1] = 1;to make the code so simple!
但是他这个算法的一个问题是, 他i和j同时作为dp和原来的matrix两者的index, 然而dp的index实际上是比matrix的index多一个+1的, 所以最后的代码看起来就有点让人发懵; 我反正是很不认同这种写法, 就为了让代码短一点, 大大的降低了readability;
@jianchao.li.fighter said in 4ms O(n) DP Solution in C++ with Explanations:
Well, this problem is similar to Unique Paths. The introduction of obstacles only changes the boundary conditions and make some points unreachable (simply set to
0).Denote the number of paths to arrive at point
(i, j)to beP[i][j], the state equation isP[i][j] = P[i - 1][j] + P[i][j - 1]ifobstacleGrid[i][j] != 1and0otherwise.Now let's finish the boundary conditions. In the Unique Paths problem, we initialize
P[0][j] = 1, P[i][0] = 1for all validi, j. Now, due to obstacles, some boundary points are no longer reachable and need to be initialized to0. For example, ifobstacleGridis like[0, 0, 1, 0, 0], then the last three points are not reachable and need to be initialized to be0. The result is[1, 1, 0, 0, 0].Now we can write down the following (unoptimized) code. Note that we pad the
obstacleGridby1and initializedp[0][1] = 1to unify the boundary cases.
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));
dp[0][1] = 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];
}
};
Well, the code is accepted but it has some obvious redundancy. There are two major concerns:
- Each time when we update
path[i][j], we only needpath[i - 1][j](at the same column) andpath[i][j - 1](at the left column), so it is unnecessary to maintain the fullm*nmatrix. Maintaining two columns is enough.- There are some cases that the loop can be terminated earlier. Suppose
obstacleGrid = [[0, 1, 0, 0], [0, 1, 0, 0], [0, 1, 0, 0]], then we can see that it is impossible to reach the bottom-right corner after updating the second column since the number of paths to reach each element in the second column is0.Taken these into considerations, we write down the following optimized code.
上面第二条的观察还是有点意思的, 看看他下面的代码是怎么写的;
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<int> pre(m, 0);
vector<int> cur(m, 0);
for (int i = 0; i < m; i++) {
if (!obstacleGrid[i][0])
pre[i] = 1;
else break;
}
for (int j = 1; j < n; j++) {
bool flag = false;
if (!obstacleGrid[0][j]) {
cur[0] = pre[0];
if (cur[0]) flag = true;
}
else cur[0] = 0;
for (int i = 1; i < m; i++) {
if (!obstacleGrid[i][j]) {
cur[i] = cur[i - 1] + pre[i];
if (cur[i]) flag = true;
}
else cur[i] = 0;
}
if (!flag) return 0;
swap(pre, cur);
}
return pre[m - 1];
}
};
也没有说pre和cur代表什么, 那么我就自己找他们从哪来的, 可以看到是一个长度为m的向量, 那么基本可以猜测到, 其实对应的就是两个column了; 然后flag的作用其实也不难, 检测的应该是at least one 1 in cur;
当然如果没有做到像上面分析的那样理解, 那么就按照自己解释的虚实结合, 找个例子算算看, 应该是不难理解的;
Further inspecting the above code, keeping two vectors only serve for the purpose of recovering
pre[i], which is simplycur[i]before its update. So we can use only one vector and the space is further optimized.
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<int> cur(m, 0);
for (int i = 0; i < m; i++) {
if (!obstacleGrid[i][0])
cur[i] = 1;
else break;
}
for (int j = 1; j < n; j++) {
bool flag = false;
if (obstacleGrid[0][j])
cur[0] = 0;
else flag = true;
for (int i = 1; i < m; i++) {
if (!obstacleGrid[i][j]) {
cur[i] += cur[i - 1];
if (cur[i]) flag = true;
}
else cur[i] = 0;
}
if (!flag) return 0;
}
return cur[m - 1];
}
};
最后这一步优化好像我以前总结过的, 不知道是什么情况下可以自信使用了; 大概看看, 我现在其实也不好说, 不过其实也就是一个常数2的差别;
当然, 不代表面试的时候就不会被问到;
@sanghi said in 4ms O(n) DP Solution in C++ with Explanations:
Nice point there about taking a flag for the case when no path exists but the space can be improved further by simply updating the given matrix rather than keeping any vectors . Here's my code.
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& a)
{
int m = a.size();
if(m==0) return 0;
int n = a[0].size();
bool flag;
for(int i=0; i<m; i++)
{ flag=0;
for(int j=0; j<n; j++)
{
int left = (j==0) ? 0 : a[i][j-1];
int top = (i==0) ? 0: a[i-1][j];
if(i==0 && j==0 && a[i][j]==0)a[i][j]=1; // to make the first box 1
else a[i][j] = a[i][j]==1 ? 0 : left+top; //update a[i][j] to the no of paths to a[i][j]
if(a[i][j]>0) flag=1;
}
if(!flag) return 0;
}
return a[m-1][n-1];
}
};
实际上是类似的思路, 不过他这里判断的是row的通路而不是column的;
@jianchao.li.fighter said in 4ms O(n) DP Solution in C++ with Explanations:
Hi, sanghi. You code is more efficient in space. But personally I prefer to keep the input unchanged :) if we can return a value.
哦, 还用了InPlace的优化;
@vvelrathbuffalo.edu said in Java Solution using Dynamic Programming, O(1) space:
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//Empty case
if(obstacleGrid.length == 0) return 0;
int rows = obstacleGrid.length;
int cols = obstacleGrid[0].length;
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(obstacleGrid[i][j] == 1)
obstacleGrid[i][j] = 0;
else if(i == 0 && j == 0)
obstacleGrid[i][j] = 1;
else if(i == 0)
obstacleGrid[i][j] = obstacleGrid[i][j - 1] * 1;// For row 0, if there are no paths to left cell, then its 0,else 1
else if(j == 0)
obstacleGrid[i][j] = obstacleGrid[i - 1][j] * 1;// For col 0, if there are no paths to upper cell, then its 0,else 1
else
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
}
}
return obstacleGrid[rows - 1][cols - 1];
}
}
@hllowrld said in Java Solution using Dynamic Programming, O(1) space:
This is a very nice solution but the title is a bit misleading - you are using O(1) space in the sense that you are using O(1) extra space. In reality you are overwriting the original matrix, and in doing so you are using O(m * n) space. This may not be allowed in production settings.
submission没有更好的解法;
Problem Description
Follow up for "Unique Paths":
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.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.
Difficulty:Medium
Total Accepted:126.7K
Total Submissions:394.8K
Contributor:LeetCode
Companies
bloomberg
Related Topics
arraydynamic programming
Similar Questions
Unique Paths