題目
一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為 “Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish”）。
現在考慮網格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？
網格中的障礙物和空位置分別用 1 和 0 來表示。
示例 1：
輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：3x3 網格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
   示例 2：
   輸入：obstacleGrid = [[0,1],[0,0]]
   輸出：1

解題思路
本題和leetcode 62不同路徑的區別在于網格中可能存在障礙物，方法仍然是動態規劃，遞推公式為dp[i][j]=dp[i-1][0]+dp[0][j-1],但能遞推的條件是當前網格沒有障礙物。本題初始化與leetcode 62差異最大，如果首尾節點存在障礙物，則無法達到終點，直接return 0. 第一行和第一列初始化時，也要判斷當前位置是否存在障礙物，如果不存在，則初始化為1，否則默認為0.

代碼實現

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();// If the starting position or the ending position is blocked, there are no possible pathsif (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {return 0;}vector<vector<long long>> dp(m, vector<long long>(n, 0));// Initialize the first row and first columndp[0][0] = 1; // Starting positionfor (int i = 1; i < m; i++) {if (obstacleGrid[i][0] != 1) {dp[i][0] = dp[i-1][0];}}for (int j = 1; j < n; j++) {if (obstacleGrid[0][j] != 1) {dp[0][j] = dp[0][j-1];}}// Calculate the number of unique paths for each positionfor (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];}}}return dp[m-1][n-1];}
};