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

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时三种方法的运行差异。任务 20-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、堆图、邻接表、邻接矩阵。算法能解释二分查找BFS / DFS归并 / 快排 / 堆排分治动态规划回溯贪心。复杂度看到代码后能大致判断O(1) O(log n) O(n) O(n log n) O(n²) 指数级 / 阶乘级大模型前置能力如果上面都掌握再进入NumPy 数组与广播PyTorch Tensor矩阵乘法计算图与自动微分EmbeddingAttentionTransformerKV Cache推理中的 Top-K / Top-P / Beam Search训练与推理复杂度分析会明显更顺畅。