09 DP / 回溯 / 贪心 — 算法思想三件套（⚠️⚠️ 人工重点）

李永乐式比喻：你要从北京出发，经多个城市，最后到上海——

• 回溯 = 列出所有可能的路线。走到一个城市发现前面是死路，就退回上一个路口换条路走。穷举 + 剪枝。
• 动态规划 = 把路线拆成子问题：今天从北京到济南、明天从济南到南京……记录每个子问题的最短距离，避免重复计算。
• 贪心 = 每次都选"当前看起来最近"的下一个城市。不看全局，只看局部最优。

---

名词映射

英文	中文	本质	比喻
Backtracking	回溯	试错 + 撤销	走迷宫，走不通就退回来
Dynamic Programming	动态规划	拆子问题 + 记录结果	记住每次的最短路段
Greedy	贪心	每步选局部最优	每次都选最近的城市
State Transfer	状态转移	从上个状态推导当前状态	dp[i] = dp[i-1] + dp[i-2]
Memoization	记忆化	缓存已算过的结果	记住已走过的路段
Pruning	剪枝	提前剔除不可能的分支	前面堵车，直接换路

---

三种思想的对比

---

爬楼梯 DP — 最直观的案例

问题：每次可以爬 1 阶或 2 阶楼梯。爬到第 n 阶有多少种方法？

关键洞察：
  爬到第 5 阶 = 从第 4 阶上来 + 从第 3 阶上来
  因为：你只能从第 4 阶跨 1 步，或者从第 3 阶跨 2 步
  
所以：dp[5] = dp[4] + dp[3]

状态转移方程：
  dp[n] = dp[n-1] + dp[n-2]
  dp[1] = 1, dp[2] = 2  （基本情况）

这其实就是一个斐波那契数列！

核心启示：DP 不聪明，它只是不笨。它不靠灵感，靠的是系统化地记住算过的结果。AI 最擅长这个。

---

0-1 背包问题

背包容量 8kg，有 3 件物品：
  A：重量 3kg，价值 5 万
  B：重量 4kg，价值 7 万  
  C：重量 5kg，价值 8 万

怎么装最值钱？

DP 的思考方式：
  先考虑只用第 1 件物品（A），能装多少？
  再加入第 2 件物品（B），重新计算……
  这就是「子问题 + 递推」的思维。

状态定义：dp[i][w] = 前 i 件物品、容量刚好 w 时的最大价值
状态转移：dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)
  要么不装第 i 件（继承之前的结果）
  要么装第 i 件（腾出 wi 空间，加上 vi 价值）

---

企业场景

场景	对应算法思想	为什么
路径规划（导航）	DP / 最短路径	子路径最短，总路径才最短
拼车匹配	回溯 + 剪枝	穷举所有匹配方案，但通过约束剪枝
任务调度（操作系统）	贪心	最短任务优先，平均等待时间最短
压缩算法（ZIP/PNG）	贪心 Huffman 编码	高频字符用短编码，局部最优 = 全局最优
AI 对话 Token 预算	DP 背包问题	给定 Token 预算，选最有价值的信息填入上下文
搜索引擎排序	贪心 + DP 混合	既要相关度又要多样性

---

量化数据

优化场景	优化前	优化后	效果
全排列（10 元素）	回溯 362 万种排列	回溯+剪枝去掉不符合约束的	剪枝 90%+ 的分支
背包（50 件物品）	穷举 O(2^n) 宇宙年龄	DP O(n*W) 0.01 秒	效率提升万亿倍
找零钱（人民币）	回溯尝试所有组合	贪心从大到小	效率提升 99.99%

---

AI 协作指南

AI 极擅长（人类不必动手写）：
  - 实现归并/快排/堆排序的代码
  - 写出 DP 的状态转移方程代码
  - 生成回溯框架和剪枝代码
  - 分析复杂度和优化建议

人类必须自己判断的（AI 做不好的）：
  - 当前业务瓶颈是 CPU 还是内存？决定了选什么算法
  - 这个问题有最优子结构吗？决定了能不能用 DP
  - 贪心选择是安全的吗？需要反例测试
  - 数据规模是多少？决定了 O(n^2) 是否可接受
  - 需要稳定的排序吗？决定了归并还是快排

最高效的学习方式：
  - 让 AI 写所有代码，只看比喻 + 图 + 场景
  - 让 AI 出复杂度对比题，你来选算法
  - 让 AI 模拟不同数据规模下的耗时和内存占用