leetcode62. 不同路径
解题思路典型的递归: f(m,n) = f(m-1,n) + f(m,n-1)，到达当前位置的所有路径可以来自上面一格的down，也可以是左边一格的right。
# 开辟一个dp内存，空间复杂度o(m*n)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1]*n for i in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i][j-1] + dp[i-1][j]
return dp[-1][-1]
# 只用一行的dp，滚动数组，节省内存，空间复杂度o(min(m,n))
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m < n: m, n = n, m # 选择空间复杂度为min(m,n)，
dp = [1]*n
for i in range(1,m):
for j in range(1,n):
dp[j] = dp[j]+dp[j-1]
return dp[-1]
扩展
如果题目不仅仅要求路径个数，还要求返回所有路径。就不能用动态规划，只能递归求解
# 时间复杂度为2^m
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m <= 0 or n <= 0:
return []
if m == 1 and n == 1:
return [[]]
up_path = self.uniquePaths(m-1, n)
left_path = self.uniquePaths(m, n-1)
respath = []
for path in up_path:
respath.append(path+['down'])
for path in left_path:
respath.append(path+['right'])
return respath
# 用dp保存已经得到的path，空间换时间
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dppath = [[[]]*n for _ in range(m)]
def findPath(m, n):
if m < 0 or n < 0:
return []
if m == 0 and n == 0:
return [[]]
if dppath[m][n]: return dppath[m][n]
up_path = findPath(m-1, n)
left_path = findPath(m, n-1)
respath = []
for path in up_path:
respath.append(path+['down'])
for path in left_path:
respath.append(path+['right'])
dppath[m][n] = respath
return respath
return findPath(m-1 ,n-1)
题目二： 机器人走有障碍物的方格的不同路径个数
leetcode63. 不同路径 II
# dp二维数组，空间复杂度为o(m*n)
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
row, col = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0]*col for _ in range(row)]
i = 0
while i < col and obstacleGrid[0][i] == 0: # 初始化第一行，一旦有障碍物后面都为0
dp[0][i] = 1
i += 1
i = 0
while i < row and obstacleGrid[i][0] == 0: # 初始化第一列，一旦有障碍物后面都为0
dp[i][0] = 1
i += 1
for i in range(1, row):
for j in range(1, col):
if not obstacleGrid[i][j]:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
# 滚动数组, 空间复杂度为o(m)，没有办法o(min(m,n))了
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
row, col = len(obstacleGrid), len(obstacleGrid[0])
i = 0
dp = [0]*col
while i < col and obstacleGrid[0][i] == 0:
dp[i] = 1
i += 1
for i in range(1, row):
dp[0] = int(not obstacleGrid[i][0] and dp[0]) #初始化每行的第一列元素
for j in range(1, col):
if obstacleGrid[i][j]:
dp[j] = 0
continue
dp[j] = dp[j-1] + dp[j]
return dp[-1]
扩展
如果题目不仅仅要求路径个数，还要求返回所有路径。就不能用动态规划，同样也是递归求解。
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m, n = len(obstacleGrid), len(obstacleGrid[0])
def findPath(m, n):
if m < 0 or n < 0 or obstacleGrid[m][n]==1:
return []
if m == 0 and n == 0:
return [[]]
up_path = findPath(m-1, n)
left_path = findPath(m, n-1)
respath = []
for path in up_path:
respath.append(path+['down'])
for path in left_path:
respath.append(path+['right'])
return respath
return findPath(m-1 ,n-1)
# 用dppath 保存已经得到的path，空间换时间
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m, n = len(obstacleGrid), len(obstacleGrid[0])
dppath = [[[0]]*n for _ in range(m)] # 为了区分已遍历但因为有障碍物而无路径[]和未遍历的情况。设置[0]代表未遍历。
def findPath(m, n):
if m < 0 or n < 0:
return []
if obstacleGrid[m][n]==1:
dppath[m][n] = []
return []
if m == 0 and n == 0:
dppath[m][n] = [[]]
return [[]]
if dppath[m][n] != [0]: return dppath[m][n] #说明已经遍历过
up_path = findPath(m-1, n)
left_path = findPath(m, n-1)
respath = []
for path in up_path:
respath.append(path+['down'])
for path in left_path:
respath.append(path+['right'])
dppath[m][n] = respath
return respath
return findPath(m-1 ,n-1)
