LeetCode 腾讯精选练习50题 - 62, 70, 78 - 动态规划

今天我们一起掌握 leetocode 的 62, 70, 78 题。都可以用动态规划解决。

1. lc 62 - 不同路径

题目来源

• 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？
• 难度：中等

1.1 法一 - 递归

在未掌握动态规划前，看到此题直接想到的是 lc 全排列 。使用递归法求解每一个路径，然后求和。但会超时。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1: return 1
        self.m,self.n = m,n 
        x,y = 0,self.n - 1
        self.res = []
        self.recursion(x,y,[]) 
        return len(self.res)

    def recursion(self, x, y, solution):
        print(x,y)
        if x == self.m - 1 and y == 0:
            self.res.append(solution) 
            return 
        if x+1 <= self.m-1 and y >= 0: 
            solution.append(1) # 右走一步 solution 加入 1 
            self.recursion(x+1,y,solution)
        if x <= self.m-1 and y-1 >= 0: 
            solution.append(2) # 下走一步 solution 加入 2 
            self.recursion(x,y-1,solution)    

我们可以采用记忆性递归，将每一次递归计算的结果储存在hashmap中，从而减少运算。每一次递归的计算应该是到每个点的路径数量。如果像上面一样递归获取每一条可能的路径，将难以记忆性递归。

1.2 法二 - 动态规划

首先需要确认该问题是否符合动态规划解题要求。

• 动态规划适合解决的问题模型符合"一个模型三个特性"
• 一个模型可以概括为:多阶段决策最优解模型;
• • 本题目第一行是已经定好了都是1,在第二行的时候,每个方格的值都是该方格左边的格和该方格上边的格的总和,以此类推,满足.
• 特性1:最优子结构;每个阶段的状态或值都是通过前面阶段的状态或值推导出来的,满足.
• 特性2:无后效性;每个阶段的状态值一旦确定之后,是不受后面阶段状态值所影响的,满足.
• 特性3:重复子问题;从递归解法中就能看出来有重复子问题的计算,满足.

接下来,该分析如何套用动态规划解题步骤。

这个矩形的左边和上边的每一个格子，都是只能通过一个路径到达。其余每一个格子都只能通过左边和上边两个方向到达。

因此，首先，定义二维数组保存路径条数。我们只有用一个二维数组储存到达每一个格子的路径总和，就能求得到达每一个格子的路径数。最终返回到达最终格子的路径数即可。

然后分阶段阶段,每一横行的处理就是一个阶段,通过上一行就能推导出下一行的状态值，在每一个阶段中,同一行中的方格,是其左边方格的值加上一行方格的总和。

最后返回二维数组最后一个元素的值即可。

复杂度：

• 时间复杂度：O(mn)。
• 空间复杂度：O(mn)，即为存储所有状态需要的空间。注意到 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n m≤n，这样空间复杂度降低至 O(min(m,n))。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1: return 1
        dp = [[1 for _ in range(m)] for _ in range(n)]
        for i in range(1,n):
            for j in range(1,m):
                dp[i][j] = dp[i][j-1]+dp[i-1][j]
        return dp[n-1][m-1]

1.3 法三：- 公式

2. lc 70 - 爬楼梯

题目来源

• 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。
• 难度：简单

2.1 解题思路 - 动态规划

本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和：

1. 爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶；

2. 爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶；

所以我们得到公式 dp[n]=dp[n−1]+dp[n−2]

同时需要初始化 dp[0]=1（爬到第一阶梯） 和 dp[1]=2（爬到第二阶梯）。

2.2 时间复杂度

• 时间复杂度： O(n)
• 空间复杂度： O(n)。可以优化到O(1)

2.3 代码

class Solution:
    def climbStairs(self, n: int) -> int:
        if n in [1,2]: return n
        dp = [1,2] + [0 for _ in range(n-2)]
        for i in range(2,len(dp)):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1] 

3. lc 78 - 子集

题目来源

• 给你一个整数数组 nums ，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。 提示：
• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• 难度：中等

3.1 解题思路 - 递归

1. 开始设输出子集为空；

2. 遍历数组candidates，对于其中的每一个数，每一步都向输出子集中所有子集添加这个整数，并且生成新的子集。

掌握了这个思路后，也可以用动态规划和回溯法解决。

3.2 时间复杂度

• 时间复杂度：O(n*2^n) 每次递归中操作：最多复制2^n。
• 空间复杂度：O(n*2^n) 最多2^n个子集。每个子集长度最多为 n。

3.3 代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.length = len(nums)
        if self.length == 0: return []
        self.res = []
        self.res.append([])
        self.recursion(nums)
        return self.res 

    def recursion(self, candidates):
        if len(candidates) == 0: 
            return 
        tmp = self.res.copy() # 复制除去candidates外元素形成的子集 

        # 添加candidates中第一个元素到 tmp 中每一个子集
        for i in range(len(tmp)): 
            self.res.append(tmp[i]+[candidates[0]])  
        del candidates[0] # 用完这个元素，从 candidates中移除
        self.recursion(candidates)

复习

学习到了一些解决这些题目可以用到的小技巧：https://blog.csdn.net/qq_32844743/article/details/112851110

1. @lru_cache: 放在class下方。使用了LRU缓存算法，将函数算过的结果缓存下来，可以避免重复计算。

参考

[1] LeetCode 数组：62. 不同路径（动态规划 带记忆的递归）. https://www.cnblogs.com/take-it-easy/p/13445490.html

[2] 78. 子集 Subsets【LeetCode 力扣官方题解】. https://www.bilibili.com/video/BV1154y1R72Q?from=search&seid=10489858157684164076