贪心

贪心策略

一. 常见贪心方法归类

朴素贪心（通过确定性的贪心步骤得出最优解）

1. 最优化策略： 每次都选当前最优策略

• 适用条件

1.1. 有明确的阶段，切每个阶段的决策都很清晰

可以分成多个轮，每轮都是一个阶段，每个阶段做的事情是个原子事件，做的事情还都类似 （一个选择，一个操作，一个切割…），阶段一定似乎按顺序执行

对于 `K（1≤K≤N）`个阶段，前 K 轮的最优决策集合成为局部最优解，当 `K = N` 时，成为全局最优解

1.2 一个阶段的局部最优解，一定是前面阶段局部最优解得到的 (最优子结构)

1.3 后面阶段的决策，不会影响到掐面阶段的决策 （无后效性）

• 解题步骤

1.4 划分问题的决策和阶段

1.5 验证最优子结构和无后效性

2. 构造法: 通过归纳总结找到规律，直接推导答案

3. 二分答案： 通过答案反推，验证合法性从而确定最优解