?LeetCode刷題實(shí)戰(zhàn)63：不同路徑 II

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問(wèn)題叫做?不同路徑II，我們先來(lái)看題面：

https://leetcode-cn.com/problems/unique-paths-ii/

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

題意

示例?1:

輸入:
[
? [0,0,0],
? [0,1,0],
? [0,0,0]
]
輸出: 2

解釋:
3x3 網(wǎng)格的正中間有一個(gè)障礙物。
從左上角到右下角一共有 2?條不同的路徑：
1.?向右 -> 向右 -> 向下 -> 向下
2.?向下 -> 向下 -> 向右 -> 向右

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