不同路径II
可以用动态规划解决，$dp[i][j]$表示从$(0,0)$到$(i,j)$的路径总数，$u[i][j]$表示坐标$(i,j)$是否有障碍物。那么我们可以得到：
如果$u[i][j]==1$，说明$(i,j)$处有障碍：
$$
dp[i][j] = 0
$$如果$u[i][j]==0$，说明$(i,j)$没障碍，那么坐标$(i,j)$处的路径总数可以由坐标$(i-1,j)$和$(i,j-1)$得到。
$$
dp[i][j] = dp[i-1][j] + dp[i][j-1]
$$
1 | class Solution { |
2 | public int uniquePathsWithObstacles(int[][] obstacleGrid) { |
3 | int m = obstacleGrid.length; |
4 | int n = obstacleGrid[0].length; |
5 | int[][] dp = new int[m][n]; |
6 | dp[0][0] = obstacleGrid[0][0]==1 ? 0:1; |
7 | for(int i=1; i<m; i++){ |
8 | dp[i][0] = obstacleGrid[i][0]==0 ? dp[i-1][0]:0; |
9 | } |
10 | for(int j=1; j<n; j++){ |
11 | dp[0][j] = obstacleGrid[0][j]==0 ? dp[0][j-1]:0; |
12 | } |
13 | for(int i=1; i<m; i++){ |
14 | for(int j=1; j<n; j++){ |
15 | if(obstacleGrid[i][j] == 1){ |
16 | dp[i][j] = 0; |
17 | }else{ |
18 | dp[i][j] = dp[i-1][j] + dp[i][j-1]; |
19 | } |
20 | } |
21 | } |
22 | return dp[m-1][n-1]; |
23 | } |
24 | } |
复杂度分析：
- 时间复杂度：$O(mn)$。
- 空间复杂度：$O(mn)$。
另外可以利用滚动数组进一步减小空间复杂度。
1 | class Solution { |
2 | public int uniquePathsWithObstacles(int[][] obstacleGrid) { |
3 | int m = obstacleGrid.length; |
4 | int n = obstacleGrid[0].length; |
5 | int[] dp = new int[n]; |
6 | dp[0] = obstacleGrid[0][0]==1 ? 0:1; |
7 | for(int i=0; i<m; i++){ |
8 | for(int j=0; j<n; j++){ |
9 | if(obstacleGrid[i][j] == 1){ |
10 | dp[j] = 0; |
11 | continue; |
12 | } |
13 | if(j >= 1){ |
14 | dp[j] += dp[j-1]; |
15 | } |
16 | } |
17 | } |
18 | return dp[n-1]; |
19 | } |
20 | } |
复杂度分析：
- 时间复杂度：$O(mn)$。
- 空间复杂度：$O(n)$。