贪心与动态规划
贪心算法在每一步固定做出一个局部选择，并且不回头修改。动态规划则会保留多个子问题的最优结果，在状态转移时比较不同选择。
两者都可能利用最优子结构，但贪心还需要额外的贪心选择性质。只有最优子结构而没有贪心选择性质时，通常需要动态规划或其他方法。
| 对比维度 | 贪心 | 动态规划 |
|---|---|---|
| 决策方式 | 每一步确定一个局部选择 | 保留并比较多个状态 |
| 是否回溯 | 通常不回头 | 通过状态转移间接比较方案 |
| 关键依据 | 贪心选择性质、最优子结构 | 状态定义、转移方程、最优子结构 |
| 典型例子 | 活动选择、Huffman、Kruskal | 0-1 背包、一般找零、最长公共子序列 |
分数背包与 0-1 背包
分数背包允许切割物品。按照单位价值从高到低装入时，即使最后只装入一部分物品，也能安全地利用剩余容量，因此贪心成立。
0-1 背包不允许切割物品。单位价值最高的物品可能占据关键容量，导致整体价值下降，所以通常需要动态规划枚举容量状态。
这说明问题表面相似，并不代表选择规则可以直接复用。约束是否允许“部分选择”会改变问题结构。
找零问题与动态规划
对于面额 {1, 3, 4} 和金额 6，贪心选择 4 会得到 3 枚硬币，而最优解 3 + 3 只需要 2 枚。
动态规划可以定义 dp[x] 表示凑出金额 x 所需的最少硬币数。假设每种硬币数量不限，先设 dp[0] = 0；其他状态初始化为不可达的大值 INF。对于每个金额 x > 0，枚举所有不超过 x 的面额 coin：
text
dp[0] = 0
dp[x] = min(dp[x - coin] + 1) # 对所有 coin 且 coin <= x如果不存在满足条件的 coin，则 dp[x] 保持为 INF，表示金额 x 不可达。这里需要对每个金额状态比较不同面额，而不是在每一步只保留当前最大的面额。
贪心与回溯、穷举
- 贪心：只保留当前选择，速度通常较快，但必须证明局部选择安全；
- 动态规划：合并具有重叠的子问题，避免重复计算；
- 回溯：系统探索选择空间，必要时撤销选择并剪枝；
- 穷举：检查所有候选方案，通常适合作为小规模基准或验证工具。
实际解题时，可以先写出穷举或动态规划版本帮助验证，再判断是否存在可以证明的贪心优化。
判断流程
面对一个新问题时，可以按以下流程思考：
- 是否存在明显的局部选择规则？
- 做出这个选择后，是否仍保留同类子问题？
- 能否用交换论证或归纳法证明选择安全？
- 如果不能证明，是否能构造反例？
- 如果需要比较多个选择，能否定义状态和转移方程？
- 如果状态空间很小，是否可以用穷举或回溯验证？
不要因为贪心代码短，就默认它比动态规划更合适。正确性证明和输入约束决定了方法选择。
小结
贪心适合那些“先做出安全选择”即可保留最优解的问题；动态规划适合必须比较多个子问题状态的问题；回溯和穷举则适合需要系统探索选择空间的场景。