Leetcode 063 不同路徑|| Python C 詳細題解

NO IMAGE

題目:

一個機器人位於一個 m x n 網格的左上角 (起始點在下圖中標記為“Start” )。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角(在下圖中標記為“Finish”)。

現在考慮網格中有障礙物。那麼從左上角到右下角將會有多少條不同的路徑?

網格中的障礙物和空位置分別用 1 和 0 來表示。

說明:m 和 的值均不超過 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();
}
};

 

思路比較簡單,這裡就不囉嗦太多了。