[LeetCode][Java] Unique Paths II

題目：

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.

題意：

緊跟著題目《Unique Paths》，現給出這樣一題目：

假設在格子中加入一些障礙，會出現多少存在且唯一的不同路徑呢？

障礙和空白格子分別被標記為1?and?0?.

比方一個3x3的格子中的中間存在一個障礙，例如以下所看到的：

[[0,0,0],[0,1,0],[0,0,0]
]

總的路徑數為2.

算法分析：

? ? ?思路與題目《Unique Paths》類似，不同之處為：

? ? ?初始化邊界上行和列時，出現障礙。后面路徑數dp的都是0

? ? ?中間的格子出現障礙時，該格子dp表示的路徑數直接填0

AC代碼：

public class Solution 
{public int uniquePathsWithObstacles(int[][] obstacleGrid) {if(obstacleGrid==null||obstacleGrid.length==0)return 0;int m = obstacleGrid.length;int n = obstacleGrid[0].length;int [][] dp = new int[m][n];for(int i = 0; i < m; i++){if(obstacleGrid[i][0]!=1)dp[i][0] = 1;else break;}for(int j = 0; j < n; j++){if(obstacleGrid[0][j]!=1)dp[0][j] = 1;else break;}for(int i = 1; i < m; i++){for(int j = 1; j< n; j++){if(obstacleGrid[i][j]!=1)dp[i][j] = dp[i-1][j] + dp[i][j-1];elsedp[i][j]=0;}}return dp[m-1][n-1];}
}