数据结构与算法-动态规划、回溯与贪心-三亩地-编程学习日记

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]，有两种选择：

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

因此：

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. 回溯：做选择、走下去、失败后恢复现场

教材将回溯过程总结为：

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

模板可以抽象成：

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 个；
从左到右处理“右边评分更高”；
从右到左处理“左边评分更高”；
取能同时满足两侧约束的数量。

这个问题很适合体会：

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

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：爬楼梯三种写法

分别实现：

朴素递归；
记忆化递归；
自下而上迭代。

记录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. 五天综合习题

第一组：复杂度

分析以下算法：

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

要求同时写：

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

第二组：数据结构选型

为下面场景选结构：

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

候选：

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

第三组：算法模式识别

判断更接近：

分治 / DP / 回溯 / 贪心

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

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

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

输入：

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

要求实现：

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

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

20. 自测答案与提示

点击查看

数据结构选型

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

算法模式

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

0-1 背包倒序

如果正序更新：

dp[j]

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

dp[j - weight]

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

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

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

数据结构

能解释：

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

算法