題目：
一個機器人位於一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。
現在考慮網格中有障礙物。那麼從左上角到右下角將會有多少條不同的路徑？
網格中的障礙物和空位置分別用 1 和 0 來表示。
說明：m 和 n 的值均不超過 100。
示例 1:
輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: 2
解釋:
3x3 網格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
既然題目提示用dp來做，那就按它的意思來好了，畢竟它的上一道同型別的題也是可以用dp做的。
演算法過程：
這道題不同就在於有個障礙物，對於障礙物，我們是永遠到不了的，所以設定它的dp的值為0。接下來就是一樣的操作罷了。
Python：
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m = len(obstacleGrid)
if m == 0:
return 0
n = len(obstacleGrid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
#先把橫行和豎行填好
for i in range(m):
if obstacleGrid[i][0] != 1:
dp[i][0] = 1
else:#遇到障礙物就跳出，因為後面的都是0
break
for i in range(n):
if obstacleGrid[0][i] != 1:
dp[0][i] = 1
else:
break
#開始填最大的部分
for i in range(1, m):
for j in range(1, n):
#不是障礙物才填
#是障礙物的話預設以及為0了
if obstacleGrid[i][j] != 1:
dp[i][j] = dp[i-1][j] dp[i][j-1]
#返回最後一個值
return dp[m-1][n-1]
這裡因為本人最近在自學C ，所以補充C 的程式碼：
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) return 0;
vector<vector<int> > dp(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0));
for (int i = 0; i < obstacleGrid.size(); i) {
for (int j = 0; j < obstacleGrid[i].size(); j) {
//遇到障礙物設為0
if (obstacleGrid[i][j] == 1) dp[i][j] = 0;
//一開始的點設為1
else if (i == 0 && j == 0) dp[i][j] = 1;
//等於上一項，其實也就是等於1或者0，與pythoN程式碼效果相同
else if (i == 0 && j > 0) dp[i][j] = dp[i][j - 1];
else if (i > 0 && j == 0) dp[i][j] = dp[i - 1][j];
//動態轉移方程
else dp[i][j] = dp[i - 1][j] dp[i][j - 1];
}
}
return dp.back().back();
}
};
思路比較簡單，這裡就不囉嗦太多了。