题目
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.
The total number of unique paths is 2.
Note: m and n will be at mZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3QgMTAwLjxicj4KCjxicj4KCjxoMj7LvMK3MTwvaDI+Cr+0tb3V4rXAzOLEv6OsztK1xLXa0ru3tNOmysfJ7rbI08XPyMvRy/ejrNXi0fm/ydLUutzH4cvJtcS78cihtNPG8LXjtb3W1bXj09C8uMz1wre+tqOsyrXP1re9t6i/ydLUyrnTw7XduemjrLWxyLvSsr/J0tTTw9W7Cjxicj4KCjxoMz60+sLrPC9oMz4KPHByZSBjbGFzcz0="brush:java;">public class Solution { public static int res = 0; public static int uniquePathsWithObstacles(int[][] obstacleGrid) { int btx, bty, edx, edy; btx = bty = 0; edy = obstacleGrid[0].length - 1; edx = obstacleGrid.length - 1; if (obstacleGrid == null || obstacleGrid[edx][edy] == 1) { return 0; } res = 0; dfsMatrix(btx, bty, edx, edy, obstacleGrid); return res; } public static boolean checkOverBoundary(int x, int y, int edx, int edy) { boolean flag = false; if (x < 0 || x > edx || y < 0 || y > edy) { flag = true; } return flag; } public static void dfsMatrix(int btx, int bty, int edx, int edy, int[][] obstacleGrid) { if (btx == edx && bty == edy) { res += 1; } else { // go right int rx = btx; int ry = bty + 1; if (!checkOverBoundary(rx, ry, edx, edy) && obstacleGrid[rx][ry] == 0) { dfsMatrix(rx, ry, edx, edy, obstacleGrid); } // go down int dx = btx + 1; int dy = bty; if (!checkOverBoundary(dx, dy, edx, edy) && obstacleGrid[dx][dy] == 0) { dfsMatrix(dx, dy, edx, edy, obstacleGrid); } } } }
无奈这道题目应该不是考察dfs，因此采用上述解法会导致超时
思路2
既然不能用递归，只能考虑动态规划了，其实跟Unique path类似，设dp[i][j]为从(0，0)到（i，j）的路径数，则状态方程如下：
代码
public class Solution {
public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
int i, j, n = obstacleGrid.length, m = obstacleGrid[0].length, dp[][] = new int[n][m];
if (obstacleGrid == null || obstacleGrid[n - 1][m - 1] == 1 || obstacleGrid[0][0] == 1) {
return 0;
}
// initial dynamic matrix
for (i = 0; i < n; i ++) {
if (obstacleGrid[i][0] == 0) {
dp[i][0] = 1;
} else {
break;
}
}
while (i < n) {
dp[i][0] = 0;
i ++;
}
for (j = 0; j < m; j ++) {
if (obstacleGrid[0][j] == 0) {
dp[0][j] = 1;
} else {
break;
}
}
while (j < m) {
dp[0][j] = 0;
j ++;
}
// dynamic process
for ( i = 1; i < n; i ++) {
for ( j = 1; j < m; j ++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
}
return dp[n - 1][m - 1];
}
}