数据结构与算法-动态规划、回溯与贪心

1. 三类算法的核心差别

先用一句话区分：

动态规划 DP

有重复子问题：把子问题答案保存下来，避免重复计算。

回溯 Backtracking

在候选空间中做选择，走不通就撤销并换路。

贪心 Greedy

每一步直接选择当前局部最优，并且通常不回头。

这三种思想都是后续算法学习中非常重要的“问题求解模板”。

2. 动态规划与分治的关系

教材指出，DP 与分治都把大问题拆成子问题。

区别是：

分治

子问题通常相互独立。

动态规划

子问题存在重叠。

如果不保存结果，会重复计算同一子问题。

因此 DP 的核心可以概括为：

定义状态 → 找到状态转移 → 确定初始状态 → 确定计算顺序 → 得到最终状态

3. 两种 DP 实现方式

教材介绍：

自上而下：记忆化递归

从原问题出发递归求解，把已经算过的结果缓存。

自下而上：迭代

从最小子问题开始，按照状态依赖顺序逐步计算。

学习 DP 时建议优先掌握自下而上，因为：

• 状态关系更直观；
• 更容易分析空间；
• 更容易做滚动数组优化。

4. 案例一：爬楼梯

每次可以爬 1 或 2 阶。

到达第n阶，只可能来自：

n - 1

或：

n - 2

因此：

f(n) = f(n - 1) + f(n - 2)

教材给出递归形式：

def climb(n): if n == 1: return 1 elif n == 2: return 2 return climb(n - 1) + climb(n - 2)

但它会重复计算。

自下而上：

def climb(n): pre = 1 cur = 1 for _ in range(1, n): pre, cur = cur, pre + cur return cur

只保留前两个状态，空间可以压缩到：

O(1)

这就是 DP 中非常常见的：

状态压缩。

5. 案例二：最大连续子数组和

教材使用力扣 53。

定义：

f(i) = 以位置 i 结尾的最大连续子数组和

对于nums[i]，有两种选择：

1. 接在前面的连续子数组后面；
2. 从当前位置重新开始。

因此：

f(i) = max( f(i - 1) + nums[i], nums[i] )

可写成：

def max_subarray(nums): best = nums[0] current = 0 for x in nums: if current < 0: current = 0 current += x best = max(best, current) return best

这道题最重要的是“状态定义”。

如果状态定义错了，后面的转移几乎一定写不出来。

6. 0-1 背包：理解二维 DP

有n个物品，每件物品有：

• 重量weight[i]；
• 价值value[i]。

背包容量为W。

每件物品：

只能选 0 次或 1 次

定义：

dp[i][j] = 前 i 个物品中，在容量不超过 j 时可获得的最大价值

对于第i个物品：

不选

dp[i-1][j]

选

value[i] + dp[i-1][j-weight[i]]

因此教材给出的转移思想是：

dp[i][j] = max( dp[i-1][j], value[i] + dp[i-1][j-weight[i]] )

7. 0-1 背包为什么一维优化要倒序

二维表可以压缩成：

dp = [0] * (W + 1)

教材的一维版本：

for i in range(n): for j in range(W, weights[i] - 1, -1): dp[j] = max( dp[j], values[i] + dp[j - weights[i]] )

关键是：

j 从大到小

为什么？

因为同一件物品只能使用一次。

如果从小到大更新，当前轮刚更新过的状态可能再次被使用，相当于同一件物品被重复选择。

这是今天必须真正理解的细节。

8. 完全背包：为什么改成正序

完全背包允许：

每件物品选择多次

教材给出的二维状态中，选择第i件物品后仍然可以继续使用第i件：

dp[i][j] = max( dp[i-1][j], value[i] + dp[i][j-weight[i]] )

一维优化：

for i in range(n): for j in range(weights[i], W + 1): dp[j] = max( dp[j], dp[j - weights[i]] + values[i] )

此时：

j 从小到大

因为允许使用本轮已经更新过的状态。

建议把下面这句话背下来：

0-1 背包倒序，防止同一物品重复使用；完全背包正序，允许同一物品重复使用。

9. 回溯：做选择、走下去、失败后恢复现场

教材将回溯过程总结为：

1. 选择：在决策点选择候选；
2. 探索：递归进入下一步；
3. 验证：检查路径是否合法；
4. 回溯：撤销选择，尝试其他可能。

模板可以抽象成：

def backtrack(path, choices): if 满足终止条件: 保存答案 return for choice in choices: if 不合法: continue 做选择 backtrack(...) 撤销选择

最关键的不是递归，而是：

递归回来以后必须恢复状态。

10. 全排列

教材使用力扣 46。

对：

[1, 2, 3]

要枚举所有排列。

一种原地交换写法：

def permute(nums): result = [] def backtrack(start): if start == len(nums): result.append(nums[:]) return for i in range(start, len(nums)): nums[start], nums[i] = nums[i], nums[start] backtrack(start + 1) nums[start], nums[i] = nums[i], nums[start] backtrack(0) return result

最后一行交换就是：

撤销选择

没有它，后面的搜索状态就会被污染。

11. N 皇后：回溯 + 剪枝

教材使用力扣 51。

每行放一个皇后。

每次选择列时需要检查：

• 当前列是否已有皇后；
• 主对角线是否冲突；
• 副对角线是否冲突。

教材用三个集合：

cols diag1 # row - col diag2 # row + col

来快速判断是否合法。

这体现了回溯优化的核心：

尽可能早地发现“不可能成功”的路径并剪掉。

12. 贪心：只做当前最优选择

教材定义：

每一步选择当前状态下的局部最优，希望一系列局部最优最终得到全局最优。

特征：

• 每一步选择局部最优；
• 通常不回溯；
• 并不是所有问题都能得到全局最优。

教材指出，贪心能正确得到全局最优，通常要求问题具有：

• 贪心选择性质；
• 最优子结构。

因此绝不能形成错误习惯：

“看到最优化问题就用贪心。”

必须能说明为什么局部选择不会破坏全局最优。

13. 案例：最大交换

对于一个非负整数，最多交换两个数字一次，使结果最大。

教材思路是从右向左维护右侧最大数字位置，并尝试产生更大的结果。

这是一种典型的：

利用局部最优候选缩小搜索空间。

14. 案例：分发糖果

规则：

• 每个孩子至少 1 个糖果；
• 相邻孩子中评分更高者获得更多糖果；
• 求最少糖果总数。

教材方法之一：

1. 所有人先发 1 个；
2. 从左到右处理“右边评分更高”；
3. 从右到左处理“左边评分更高”；
4. 取能同时满足两侧约束的数量。

这个问题很适合体会：

局部约束可能来自两个方向，因此一次单向扫描不一定够。

15. DP、回溯、贪心怎么快速识别

更像 DP

你发现：

• 大问题依赖更小问题；
• 同一个子问题会反复出现；
• 可以定义“状态”；
• 当前状态可以由之前状态转移得到。

关键词：

最值 / 方案数 / 是否可达 / 子序列 / 背包

不是绝对规则，但很常见。

更像回溯

你需要：

• 枚举组合；
• 枚举排列；
• 枚举路径；
• 每一步有多个候选；
• 走不通需要撤销。

关键词：

所有方案 / 排列 / 组合 / 棋盘 / 搜索空间

更像贪心

你希望：

• 每一步可以立即选一个局部最优；
• 选完不需要回头；
• 能证明局部选择不会破坏最终最优。

16. 大模型迁移理解

以下为延伸学习连接。

16.1 Greedy Decoding 就带有典型贪心味道

生成式模型在每一步都可以得到下一个 token 的分数。

一种最简单的解码方式是：

每一步选择当前概率最高的 token

这在思想上就是局部贪心。

但要注意：

当前每一步概率最高，并不保证整段序列一定是全局最优序列。

这也正好对应了今天对贪心算法局限性的理解。

16.2 Beam Search 是“保留多个候选路径”的搜索思想

相比只保留一个局部最佳选择，Beam Search 会保留若干候选序列继续扩展。

学习树、堆、排序、搜索之后再看 Beam Search，会看到这些基础知识开始汇合：

• 搜索树；
• 候选集合；
• 分数排序；
• Top-K；
• 剪枝。

16.3 DP 的真正价值是“复用中间结果”

后续阅读机器学习、NLP、序列算法时，会不断遇到：

某个中间结果已经算过，就不要重复计算

缓存、状态复用、动态规划虽然具体实现不同，但背后的计算思想高度相关。

17. 今日编码任务

任务 1：爬楼梯三种写法

分别实现：

1. 朴素递归；
2. 记忆化递归；
3. 自下而上迭代。

记录n = 35时三种方法的运行差异。

任务 2：0-1 背包

输入：

weights = [1, 2, 3] values = [3, 2, 6] W = 3

分别实现：

• 二维 DP；
• 一维 DP。

解释为什么一维版本必须倒序遍历容量。

任务 3：全排列

实现：

permute([1, 2, 3])

要求：

• 使用回溯；
• 每轮递归输出当前 path 或 nums；
• 能指出“选择”和“撤销选择”分别是哪一行。

18. 五天综合习题

第一组：复杂度

分析以下算法：

1. 遍历长度为n的数组；
2. 两层完整嵌套遍历；
3. 二分查找；
4. 归并排序；
5. 全排列。

要求同时写：

• 时间复杂度；
• 空间复杂度；
• 复杂度的主要来源。

第二组：数据结构选型

为下面场景选结构：

1. 浏览器后退历史；
2. 请求排队；
3. user_id -> user_info；
4. 保存层级目录；
5. 表示城市道路连接；
6. 动态保留最大的 10 个分数。

候选：

栈 / 队列 / 哈希表 / 树 / 图 / 堆

第三组：算法模式识别

判断更接近：

分治 / DP / 回溯 / 贪心

1. 把数组一分为二分别排序后合并；
2. 计算前i个物品、容量j下的最优价值；
3. 枚举 N 皇后的所有合法摆法；
4. 每一步直接选当前最优候选且不回退。

19. 大模型方向综合小项目

完成一个“小型候选生成与筛选器”。

输入：

candidates = [ ("token_A", 0.12), ("token_B", 0.55), ("token_C", 0.08), ("token_D", 0.21), ("token_E", 0.04), ]

要求实现：

1. 使用哈希表保存token -> score；
2. 使用堆找出 Top-3；
3. 按分数排序输出；
4. 分析各步骤复杂度；
5. 如果候选规模从 5 增加到 5,000,000，说明为什么不能只关注“代码是否能运行”。

这个练习不模拟真实 Transformer，只是把五天的数据结构与算法知识迁移到“大模型候选处理”这一类工程场景。

20. 自测答案与提示

点击查看

数据结构选型

1. 浏览器后退：栈
2. 请求排队：队列
3. user_id -> user_info：哈希表
4. 层级目录：树
5. 城市道路：图
6. 动态 Top-10：堆

算法模式

1. 归并排序：分治
2. 0-1 背包：动态规划
3. N 皇后：回溯
4. 局部最优且不回退：贪心

0-1 背包倒序

如果正序更新：

dp[j]

可能使用本轮刚更新过的：

dp[j - weight]

相当于同一物品被重复选择，从 0-1 背包错误地变成“可重复使用”的效果。

21. 五天结束后的能力检查

完成五天学习后，建议不看资料完成下面的口述测试。

数据结构

能解释：

• 数组与链表；
• 栈与队列；
• 哈希表；
• 树、BST、堆；
• 图、邻接表、邻接矩阵。

算法

能解释：

• 二分查找；
• BFS / DFS；
• 归并 / 快排 / 堆排；
• 分治；
• 动态规划；
• 回溯；
• 贪心。

复杂度

看到代码后能大致判断：

O(1) O(log n) O(n) O(n log n) O(n²) 指数级 / 阶乘级

大模型前置能力

如果上面都掌握，再进入：

1. NumPy 数组与广播；
2. PyTorch Tensor；
3. 矩阵乘法；
4. 计算图与自动微分；
5. Embedding；
6. Attention；
7. Transformer；
8. KV Cache；
9. 推理中的 Top-K / Top-P / Beam Search；
10. 训练与推理复杂度分析；

会明显更顺畅。