企业官网建设流程全解析

基础算法精讲·题目汇总：灵茶山艾府 - 【基础算法精讲】- GitHub

视频：灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频

力扣最全 DP 题单：分享丨【算法题单】动态规划（入门/背包/划分/状态机/区间/状压/数位/树形/优化） - 讨论 - 力扣（LeetCode）

17 从记忆化搜索到递推

推荐学习路线：二叉树递归 -> 回溯 -> 记忆化搜索 -> 递推

动态规划的核心是状态定义和状态转移方程

子集型回溯：选或不选 / 选哪个，两种思路

课程讲解

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 cache

class 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] * (n+2) for i, x in enumerate(nums): f[i+2] = max(f[i+1], f[i] + x) return f[n+1]

【答疑】为什么 nums【i】 中的 i 不需要 +2。 第一，这会导致 nums【0】 和 nums【1】 无法算进答案中。 第二，当 i=n-1 时，i+2=n+1，这会导致 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. 爬楼梯 II

213. 打家劫舍 II

740. 删除并获得点数

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] * (target+1) for _ in range(n+1)] f[0][0] = 1 for i, x in enumerate(nums): for c in range(target+1): if c < x: f[i+1][c] = f[i][c] else: f[i+1][c] = f[i][c] + f[i][c-x] return f[n][target]

每时每刻只有两个数组中的元素在参与状态转移：

只需要用到两个数组，把所有的和 i 相关的都改成 模2，这样就把空间复杂度优化到 O(target)

n = len(nums) f = [[0] * (target+1) for _ in range(2)] f[0][0] = 1 for i, x in enumerate(nums): for c in range(target+1): if c < x: f[(i+1)%2][c] = f[i%2][c] else: f[(i+1)%2][c] = f[i%2][c] + f[i%2][c-x] return f[n%2][target]

优化成一个一维数组：

倒着算就不会被覆盖

n = len(nums) f = [0] * (target+1) 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]

如果是至多为target：

def findTargetSumWays(nums, target): target += sum(nums) if target < 0: return 0 target //= 2 # 问题变成：从 nums 中选出一个子集，使子集和 <= target 的方案数 f = [1] * (target+1) # 初始化为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)

如果是至少为target：

def findTargetSumWays(nums, target): target += sum(nums) if target < 0: return 1 << len(nums) target = (target + 1) // 2 f = [0] * (target+1) 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)] # 把所有 c<=0 的状态都记录到 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. 零钱兑换

完全背包的一种变形，把物品价值看成1

class 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] * (amount+1) for _ in range(n+1)] f[0][0] = 0 for i, x in enumerate(coins): for c in range(amount+1): # c表示剩余容量 if c < x: f[i+1][c] = f[i][c] else: f[i+1][c] = min(f[i][c], f[i+1][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] * (amount+1) f[0] = 0 for x in coins: for c in range(x, amount+1): f[c] = min(f[c], f[c-x] + 1) ans = f[amount] return ans if ans < inf else -1

循环顺序总结：

一维数组：

• 01背包：倒序
• 完全背包：正序

二维数组： 一般都写正序

变形，如求方案数的话，有：

• 至多
• 恰好
• 至少

课后作业

2915. 和为目标值的最长子序列的长度

416. 分割等和子集

2787. 将一个数字表示成幂的和的方案数

518. 零钱兑换 II

279. 完全平方数

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] * (m+1) for _ in range(n+1)] for i, x in enumerate(text1): for j, y in enumerate(text2): if x == y: f[i+1][j+1] = f[i][j] + 1 else: f[i+1][j+1] = max(f[i][j+1], f[i+1][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 j+1 # 一个字符串为空，需要把另一个字符串都去掉 if j < 0: return i+1 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] = j，f[i][0] = i

class Solution: def minDistance(self, word1: str, word2: str) -> int: n = len(word1) m = len(word2) f = [[0] * (m+1) for _ in range(n+1)] f[0] = list(range(m+1)) # f[0][j] = j for i, x in enumerate(word1): f[i+1][0] = i+1 # f[i][0] = i for j, y in enumerate(word2): if x == y: f[i+1][j+1] = f[i][j] else: f[i+1][j+1] = min(f[i+1][j], f[i][j+1], 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. 使数组严格递增