一個(gè)機(jī)器人位于一個(gè)?m x n?網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。

機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。

問(wèn)總共有多少條不同的路徑？

看見(jiàn)題目我們首先用動(dòng)態(tài)規(guī)劃四步曲進(jìn)行分析。

dp數(shù)組應(yīng)該怎么看？我們回想一下爬樓梯，其實(shí)本題和他也沒(méi)什么區(qū)別，唯一不同的我們這個(gè)是二維的，既然要記錄總共的路徑那么我們就定義一個(gè)二維數(shù)組，每一個(gè)記錄到該點(diǎn)要走多少步，和爬樓梯一樣，他是只能走一步或者兩步，我們是只能向下或者向右，所以我們每一點(diǎn)的值就等于他上面的和左邊的和，畢竟他們倆是不重復(fù)的，加起來(lái)就是能到該點(diǎn)的所有的路徑。

所以得到遞推公式：?dp[i][j] = dp[i-1][j]+dp[i][j-1];

那么我們?cè)趺闯跏蓟?#xff0c;首先我們看一下遞推公式，需要-1，那就意味著我們的第一行和第一列都是要初始化的，所以我們直接把他們賦值成1就可以了。

我們直接上代碼

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i = 0;i<m;i++){dp[i][0] = 1;for(int j = 0;j<n;j++){dp[0][j] = 1;}}for(int i = 1;i<m;i++){for(int j = 1;j<n;j++){dp[i][j] = dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
}  

給定一個(gè)?m x n?的整數(shù)數(shù)組?grid。一個(gè)機(jī)器人初始位于?左上角（即?grid[0][0]）。機(jī)器人嘗試移動(dòng)到?右下角（即?grid[m - 1][n - 1]）。機(jī)器人每次只能向下或者向右移動(dòng)一步。

網(wǎng)格中的障礙物和空位置分別用?1?和?0?來(lái)表示。機(jī)器人的移動(dòng)路徑中不能包含?任何?有障礙物的方格。

返回機(jī)器人能夠到達(dá)右下角的不同路徑數(shù)量。

測(cè)試用例保證答案小于等于?2 * 109。

示例 1：

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

這一題是上一題的變種，我們的路上有障礙了，我們?nèi)绾我?guī)避這個(gè)障礙呢?，首先就是在路程中把障礙物都變成讓他沒(méi)辦法走，一開(kāi)始我就只加了這一個(gè)邏輯，但是運(yùn)行起來(lái)發(fā)現(xiàn)不對(duì)，后來(lái)我思考了一下發(fā)現(xiàn)還有問(wèn)題，因?yàn)槲覀兊某跏蓟灿袉?wèn)題，如果第一排就有障礙，后面的都是0啊都得不到值，所以把這倆邏輯加進(jìn)來(lái)這個(gè)問(wèn)題就解決啦

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;if (obstacleGrid[0][0] == 1) {return 0;}// 初始化 dp 數(shù)組int[][] dp = new int[m][n];dp[0][0] = 1; // 起點(diǎn)路徑數(shù)為 1for (int j = 1; j < n; j++) {if (obstacleGrid[0][j] == 1) {break; // 遇到障礙物，后續(xù)路徑都為 0}dp[0][j] = 1;}// 初始化第一列for (int i = 1; i < m; i++) {if (obstacleGrid[i][0] == 1) {break; // 遇到障礙物，后續(xù)路徑都為 0}dp[i][0] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) {dp[i][j] = 0; // 當(dāng)前格子有障礙物，路徑數(shù)為 0} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 狀態(tài)轉(zhuǎn)移}}}return dp[m - 1][n - 1];}
}