算法类型
一、贪心（Greedy）
理解
在每一步的选择中采取当前状态下的最优解，但无法保证全局最优解。
那我如何确保我做的题就适用于此？
解题策略在于，必须证明每一步所作的贪心选择最终导致问题的整体最优解。百度百科给出了全面的解释：证明过程大致是，首先考察问题的整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题的规模简化为规模更小的类似子问题。 然后用数学归纳法证明合理性。
对于前端开发来说，适用场景：
| 问题类型 | 贪心策略 | 经典例子 |
|---|---|---|
| 区间调度 | 每次选结束时间最早的 | 会议安排、无重叠区间 |
| 最小生成树 | Kruskal/Prim | 网络布线 |
| 哈夫曼编码 | 合并频率最小的两个节点 | 压缩算法 |
| 部分背包 | 按单位价值排序 | 货物装载（可切分） |
| 找零（特定面额） | 用最大面额优先 | 人民币/美元标准硬币 |
| 任务调度（单机） | 按最短处理时间优先 | 最小化平均等待时间 |
和DP的区别
贪心每一步局部最优解，不回溯；动态规划考虑所有可能，保留子问题结果。
两者都要求最优子结构，区别在于贪心要求更强的局部即可带来全局最优解，不满足时，只能用DP或回溯。