在力扣劃水的時候看到一道這樣的題目：
62. 不同路徑
用動态規劃的思想進行求解：
我們用 d p [ i ] [ j ] dp[i][j] dp[i][j]表示從左上角走到 ( i , j ) (i, j) (i,j) 的路徑數量，其中 i i i 和 j j j 的範圍分别是 [ 0 , m ) [0, m) [0,m) 和 [ 0 , n ) [0, n) [0,n)。
由于我們每一步隻能從向下或者向右移動一步，是以要想走到 ( i , j ) (i, j) (i,j)，如果向下走一步，那麼會從 ( i − 1 , j ) , ( i − 1 , j ) (i-1, j),(i−1,j) (i−1,j),(i−1,j) 走過來；如果向右走一步，那麼會從 ( i , j − 1 ) , ( i , j − 1 ) (i, j-1),(i,j−1) (i,j−1),(i,j−1) 走過來。是以我們可以寫出動态規劃轉移方程：
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][j] = dp[i-1][j]+dp[i][j-1] dp[i][j]=dp[i−1][j]+dp[i][j−1]
當然如果 i = 0 或 者 j = 0 i=0或者j=0 i=0或者j=0,dp的值都是0
最終的答案即為 d p [ m − 1 ] [ n − 1 ] dp[m-1][n-1] dp[m−1][n−1]。
代碼如下：
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0 for i in range(n)]for j in range(m)] #動态規劃數組
for i in range(m):
for j in range(n):
dp[i][j] = dp[i-1][j] + dp[i][j-1] if i-1>=0 and j-1>=0 else 1
return dp[m-1][n-1]
但是每次看到這樣的路徑的題目，腦子裡就不自覺認為dfs大法好啊，試了一下dfs,報了逾時錯誤：
同樣再看一個題目：
63. 不同路徑 II
動态規劃解決，和第一個一模一樣的思路，隻是在初始值的設定方面和第一個有點不一樣，當這個點為1 的時候，是沒有一條路徑能夠抵達的。
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[0 for i in range(n)] for j in range(m)]
dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 1
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
if i==0 and j > 0:
dp[i][j] = dp[i][j-1] if obstacleGrid[i][j] == 0 else 0
if j == 0 and i>0:
dp[i][j] = dp[i-1][j] if obstacleGrid[i][j] == 0 else 0
elif i-1>=0 and j-1>=0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
當然，我看見路徑問題，肯定是寫了個深搜：
同樣也是逾時。
再看一個求路徑數量的：
797. 所有可能的路徑
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
res = [] # 總的
temp = [] # 臨時的路徑
n = len(graph) - 1
def dfs(x):
if x == n:
res.append(temp[:])
return
for y in graph[x]: # 所有與x連接配接的都有可能是下一個y
temp.append(y)
dfs(y)
temp.pop()
temp.append(0)
dfs(0)
return res
這個題目深搜又能過了。
再來一個求最短路徑的：
劍指 Offer II 099. 最小路徑之和
動态規劃解決，和一開始的思路是一模一樣的，代碼如下：
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dp = [[0 for i in range(n)] for j in range(m)]
dp[0][0] = grid[0][0]
for i in range(m):
for j in range(n):
if i-1>=0 and j-1>=0:
dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
elif i==0 and j>0:
dp[i][j] = dp[i][j-1] + grid[i][j]
elif j == 0 and i>0:
dp[i][j] = dp[i-1][j]+grid[i][j]
return dp[m-1][n-1]
這個動态規劃能過，試着寫一個回溯的，依舊是逾時：