題目62：不同路徑
一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。
問總共有多少條不同的路徑？
例如，上圖是一個7 x 3 的網格。有多少可能的路徑？
示例1：
輸入: m = 3, n = 2輸出: 3解釋:從左上角開始，總共有 3 條路徑可以到達右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右
輸入: m = 7, n = 3輸出: 28
1 <= m, n <= 100題目數據保證答案小于等于
2 * 10 ^ 9
分析
由于機器人每次只能向下或者向右移動一步，當前節點只能從上面節點或者左邊節點走過來，dpi表示走到當前節點共有多少條路徑，則路徑數dpi=dpi-1 + dpi，第一排和第一列的路徑數肯定是1，具體可以看代碼。
代碼
class Solution {public:int uniquePaths(int m, int n) {int dp[m][n];for (int i = 0; i < n; ++i) {dp[0][i] = 1;}for (int i = 0; i < m; ++i) {dp[i][0] = 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];}};
擴展63：不同路徑II
現在考慮網格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？
分析
大體和上一題相同，只是障礙物的節點路徑數為0，第一行或者第一列某一節點為障礙物，它后面的節點全部不可達。見代碼：
代碼
class Solution {public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int row = obstacleGrid.size();int col = obstacleGrid[0].size();long long dp[row][col];bool has_obstacle = false;for (int i = 0; i < col; ++i) {if (obstacleGrid[0][i] == 1) {has_obstacle = true;}dp[0][i] = has_obstacle ? 0 : 1;}has_obstacle = false;for (int i = 0; i < row; ++i) {if (obstacleGrid[i][0] == 1) {has_obstacle = true;}dp[i][0] = has_obstacle ? 0 : 1;}for (int i = 1; i < row; ++i) {for (int j = 1; j < col; ++j) {if (obstacleGrid[i][j] == 1) {dp[i][j] = 0;} else {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}}return dp[row-1][col-1];}};