【灵神高频面试题合集17-20】动态规划（上）

基础算法精讲·题目汇总灵茶山艾府 - 【基础算法精讲】- GitHub视频灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频力扣最全 DP 题单分享丨【算法题单】动态规划入门/背包/划分/状态机/区间/状压/数位/树形/优化 - 讨论 - 力扣LeetCode17 从记忆化搜索到递推推荐学习路线二叉树递归 - 回溯 - 记忆化搜索 - 递推动态规划的核心是状态定义和状态转移方程子集型回溯选或不选 / 选哪个两种思路课程讲解198. 打家劫舍选的情况下相邻的房子是不能选的直接递归到 n-2 个房子在定义 dfs 或者 dp 数组的含义时只能表示从一些元素中算出的结果而不是从一个元素中算出的结果没有把得到的金额和作为递归的入参而是作为返回值后面记忆化要用class Solution: def rob(self, nums: List[int]) - int: n len(nums) def dfs(i): if i 0: # 没有房子可以选了 return 0 res max(dfs(i-1), dfs(i-2) nums[i]) return res return dfs(n-1)指数级时间复杂度回溯会超时记忆化搜索优化后的搜索树优化后搜索树只有 O(n) 个节点因此时间复杂度也优化到了 O(n)对于Python可以用一个 cache 装饰器原理是用一个 hashmap 记录入参和对应的返回值在 Python 中cache是 Python 3.9 版本引入的一个装饰器用于自动缓存函数的计算结果记忆化搜索非常适合深度优先搜索DFS场景可以避免重复计算大大提升运行速度具体的引入方式from functools import cacheclass Solution: def rob(self, nums: List[int]) - int: n len(nums) cache [-1] * n def dfs(i): if i 0: return 0 if cache[i] ! -1: return cache[i] res max(dfs(i-1), dfs(i-2) nums[i]) cache[i] res return res return dfs(n-1)时间复杂度状态个数 × 单个状态所需要的计算时间。前者 O(n)后者 O(1)所以时间复杂度为 O(n)空间复杂度O(n)class Solution: def rob(self, nums: List[int]) - int: n len(nums) f [0] * (n2) for i, x in enumerate(nums): f[i2] max(f[i1], f[i] x) return f[n1]【答疑】为什么 nums【i】 中的 i 不需要 2。 第一这会导致 nums【0】 和 nums【1】 无法算进答案中。 第二当 in-1 时i2n1这会导致 nums 数组越界。 另外一种理解方式是我们只是在 f 数组的开头插入了两个状态对应记忆化搜索中的 dfs(-2) 和 dfs(-1)这只会影响到 f 的下标不会影响到 nums 的下标。上面代码的空间复杂度仍然是 O(n) 的。优化空间复杂度为 O(1)class Solution: def rob(self, nums: List[int]) - int: n len(nums) f0 f1 0 for i, x in enumerate(nums): new_f max(f1, f0 x) f0 f1 f1 new_f return f1 # 最后一次算出来的 new_f课后作业70. 爬楼梯746. 使用最小花费爬楼梯3693. 爬楼梯 II213. 打家劫舍 II740. 删除并获得点数2466. 统计构造好字符串的方案数377. 组合总和 Ⅳ2266. 统计打字方案数64. 最小路径和18 0-1背包 完全背包课程讲解0-1背包# capacity背包容量 # w[i]第 i 个物品的体积 # v[i]第 i 个物品的价值 # 返回所选物品体积和不超过 capacity 的前提下所能得到的最大价值和 def zero_one_knapsack(capacity: int, w: List[int], v: List[int]) - int: n len(w) cache def dfs(i, c): if i 0: return 0 if c w[i]: # 物品体积已经超过背包剩余容量只能不选 return dfs(i-1, c) return max(dfs(i-1, c), dfs(i-1, c-w[i]) v[i]) return dfs(n-1, capacity)cache 这一行的作用是改成记忆化搜索494. 目标和class Solution: def findTargetSumWays(self, nums: list[int], target: int) - int: # 添加正数的和记为p # 添加负数的和 所有元素的和 - p s-p # target p - (s-p) 推导出 p (s target) / 2 # 问题变成从nums中选择一些数字使它们的和恰好等于 (s target) / 2 的方案数 # s target 必须是偶数 非负数 # dfs(i, c) 表示从前 i 个数中选一些数恰好组成 c 的方案数 target sum(nums) if target 0 or target % 2: # 负数或奇数方案数就是0 return 0 target // 2 n len(nums) cache def dfs(i, c): if i 0: return 1 if c 0 else 0 # c是target减到0就找到了一组方案 if c nums[i]: return dfs(i-1, c) return dfs(i-1, c) dfs(i-1, c-nums[i]) return dfs(n-1, target)时间复杂度O (n * target) 状态个数 * 每个状态所需的时间 O(1)空间复杂度O (n * target)优化空间复杂度把记忆化搜索改成递推class Solution: def findTargetSumWays(self, nums: list[int], target: int) - int: # 添加正数的和记为p # 添加负数的和 所有元素的和 - p s-p # target p - (s-p) 推导出 p (s target) / 2 # 问题变成从nums中选择一些数字使它们的和恰好等于 (s target) / 2 的方案数 # s target 必须是偶数 非负数 # dfs(i, c) 表示从前 i 个数中选一些数恰好组成 c 的方案数 target sum(nums) if target 0 or target % 2: return 0 target // 2 n len(nums) f [[0] * (target1) for _ in range(n1)] f[0][0] 1 for i, x in enumerate(nums): for c in range(target1): if c x: f[i1][c] f[i][c] else: f[i1][c] f[i][c] f[i][c-x] return f[n][target]每时每刻只有两个数组中的元素在参与状态转移只需要用到两个数组把所有的和 i 相关的都改成 模2这样就把空间复杂度优化到 O(target)n len(nums) f [[0] * (target1) for _ in range(2)] f[0][0] 1 for i, x in enumerate(nums): for c in range(target1): if c x: f[(i1)%2][c] f[i%2][c] else: f[(i1)%2][c] f[i%2][c] f[i%2][c-x] return f[n%2][target]优化成一个一维数组倒着算就不会被覆盖n len(nums) f [0] * (target1) f[0] 1 for x in nums: for c in range(target, x-1, -1): f[c] f[c] f[c-x] return f[target]如果是至多为targetdef findTargetSumWays(nums, target): target sum(nums) if target 0: return 0 target // 2 # 问题变成从 nums 中选出一个子集使子集和 target 的方案数 f [1] * (target1) # 初始化为1至多为target时不选择元素就可以作为一种合理方案 for x in nums: for c in range(target, x-1, -1): f[c] f[c] f[c-x] return f[target] # 或记忆化搜索的写法 from functools import cache def findTargetSumWays(nums, target): target sum(nums) if target 0: return 0 target // 2 n len(nums) cache def dfs(i, c): # 从前 i 个元素中选子集使子集和 c 的方案数 if i 0: return 1 if c nums[i]: return dfs(i-1, c) return dfs(i-1, c) dfs(i-1, c-nums[i]) return dfs(n-1, target)如果是至少为targetdef findTargetSumWays(nums, target): target sum(nums) if target 0: return 1 len(nums) target (target 1) // 2 f [0] * (target1) f[0] 1 # 剩余需要凑的和 0 时空集满足方案数为 1 for x in nums: for c in range(target, -1, -1): f[c] f[c] f[max(c-x, 0)] # 把所有 c0 的状态都记录到 f[0] 里 return f[target] # 或 from functools import cache def findTargetSumWays(nums, target): target sum(nums) if target 0: return 1 len(nums) target (target 1) // 2 n len(nums) cache def dfs(i, c): if i 0: return 1 if c 0 else 0 return dfs(i-1, c) dfs(i-1, c-nums[i]) return dfs(n-1, target)完全背包和 01背包的回溯 区别在选了一个物品之后i是不变的表示可以继续选第i种物品# capacity背包容量 # w[i]第 i 种物品的体积 # v[i]第 i 种物品的价值 # 每种物品可以无限次重复选 # 返回所选物品体积和不超过 capacity 的前提下所能得到的最大价值和 def unbounded_knapsack(capacity: int, w: List[int], v: List[int]) - int: n len(w) cache def dfs(i, c): if i 0: return 0 if c w[i]: return dfs(i-1, c) return max(dfs(i-1, c), dfs(i, c-w[i]) v[i]) # 唯一区别 return dfs(n-1, capacity)322. 零钱兑换完全背包的一种变形把物品价值看成1class Solution: def coinChange(self, coins: list[int], amount: int) - int: n len(coins) cache def dfs(i, c): if i 0: return 0 if c 0 else inf # inf表示不是一种合法的方案 if c coins[i]: return dfs(i-1, c) return min(dfs(i-1, c), dfs(i, c-coins[i]) 1) ans dfs(n-1, amount) return ans if ans inf else -1改成递推class Solution: def coinChange(self, coins: list[int], amount: int) - int: n len(coins) f [[inf] * (amount1) for _ in range(n1)] f[0][0] 0 for i, x in enumerate(coins): for c in range(amount1): # c表示剩余容量 if c x: f[i1][c] f[i][c] else: f[i1][c] min(f[i][c], f[i1][c-x] 1) ans f[n][amount] return ans if ans inf else -1空间优化一维数组对于完全背包正序计算是对的。空间复杂度优化到了 O(amount)class Solution: def coinChange(self, coins: list[int], amount: int) - int: n len(coins) f [inf] * (amount1) f[0] 0 for x in coins: for c in range(x, amount1): f[c] min(f[c], f[c-x] 1) ans f[amount] return ans if ans inf else -1循环顺序总结一维数组01背包倒序完全背包正序二维数组 一般都写正序变形如求方案数的话有至多恰好至少课后作业2915. 和为目标值的最长子序列的长度416. 分割等和子集2787. 将一个数字表示成幂的和的方案数518. 零钱兑换 II279. 完全平方数19 线性dp上在默认情况下子数组和子串是连续的子序列不一定是连续的课程讲解1143. 最长公共子序列 LCS在 s[i] t[j] 时只需要考虑都选的情况在 s[i] ≠ t[j] 时不需要考虑都不选的情况class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: n len(text1) m len(text2) cache def dfs(i, j): if i 0 or j 0: return 0 if text1[i] text2[j]: return dfs(i-1, j-1) 1 return max(dfs(i-1, j), dfs(i, j-1)) return dfs(n-1, m-1)时间复杂度O(nm)空间同改成递推class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: n len(text1) m len(text2) f [[0] * (m1) for _ in range(n1)] for i, x in enumerate(text1): for j, y in enumerate(text2): if x y: f[i1][j1] f[i][j] 1 else: f[i1][j1] max(f[i][j1], f[i1][j]) return f[n][m]优化成一个一维数组空间复杂度为 O(m)72. 编辑距离class Solution: def minDistance(self, word1: str, word2: str) - int: n len(word1) m len(word2) cache def dfs(i, j): if i 0: return j1 # 一个字符串为空需要把另一个字符串都去掉 if j 0: return i1 if word1[i] word2[j]: return dfs(i-1, j-1) else: return min(dfs(i-1, j), dfs(i, j-1), dfs(i-1, j-1)) 1 return dfs(n-1, m-1)改成递推初始化f[0][j] jf[i][0] iclass Solution: def minDistance(self, word1: str, word2: str) - int: n len(word1) m len(word2) f [[0] * (m1) for _ in range(n1)] f[0] list(range(m1)) # f[0][j] j for i, x in enumerate(word1): f[i1][0] i1 # f[i][0] i for j, y in enumerate(word2): if x y: f[i1][j1] f[i][j] else: f[i1][j1] min(f[i1][j], f[i][j1], f[i][j]) 1 return f[n][m]课后作业583. 两个字符串的删除操作712. 两个字符串的最小ASCII删除和97. 交错字符串1458. 两个子序列的最大点积1092. 最短公共超序列20 线性dp下课程讲解300. 最长递增子序列 LIS所谓子序列就是从数组中选择一些数且顺序和数组中的顺序是一致的回溯/动态规划对于子集型回溯用思路2更简单记忆化搜索class Solution: def lengthOfLIS(self, nums: list[int]) - int: n len(nums) cache def dfs(i): # 表示以 nums[i] 结尾的子序列长度 res 0 for j in range(i): # 枚举 i 前面的 j if nums[j] nums[i]: res max(res, dfs(j)) return res 1 # 这里的 1 表示 nums[i] ans 0 for i in range(n): ans max(ans, dfs(i)) return ans时间复杂度O(n^2)。O(n) 个状态计算每个状态需要 O(n) 的时间空间复杂度O(n)递推时空间复杂度同上class Solution: def lengthOfLIS(self, nums: list[int]) - int: n len(nums) f [0] * n for i in range(n): for j in range(i): if nums[j] nums[i]: f[i] max(f[i], f[j]) f[i] 1 return max(f)最长递增子序列 vs 最长公共子序列 是有联系的贪心二分这种方法时间复杂度优化到 O(nlogn)class Solution: def lengthOfLIS(self, nums: list[int]) - int: g [] for x in nums: j bisect_left(g, x) # 二分查找 x 在 g 中的位置 if j len(g): # j 不存在 g.append(x) else: g[j] x return len(g)空间复杂度 O(n)可以直接把 nums 当做 g 数组这样空间复杂度就优化到 O(1) 了class Solution: def lengthOfLIS(self, nums: list[int]) - int: ng 0 # 表示g的长度 for x in nums: j bisect_left(nums, x, 0, ng) # 直接在nums上二分范围是0~ng if j ng: # 表示j不存在 nums[ng] x ng 1 # g数组长度1 else: nums[j] x return ng对应到代码中就是把 bisect_left 改成 bisect_right课后作业2826. 将三个组排序1964. 找出到每个位置为止最长的有效障碍赛跑路线1671. 得到山形数组的最少删除次数2111. 使数组 K 递增的最少操作次数354. 俄罗斯套娃信封问题1626. 无矛盾的最佳球队1187. 使数组严格递增