动态规划专题【持续更新】

动态规划专题【持续更新】 题目一： 机器人走无障碍物的方格的不同路径个数

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)