题目
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.
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 most 100.
Note: m and n will be at most 100.
思路1
看到这道题目,我的第一反应是深度优先搜索,这样可以很轻松的获取从起点到终点有几条路径,实现方法可以使用递归,当然也可以用栈
代码
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]; } }