贪心算法

type

status

date

slug

summary

每个阶段作出局部最优解，最终会自然达到全局最优解

每个阶段的最优解不一定是一次性获得，可能也是需要不断回头更新（比如最长递增子序列）

区别

Greedy比DP少考虑了哪些子问题，为什么可以少考虑那些子问题，而每次只专注于求解一个子问题，通过逐步递推得到原问题的答案？

首先，整个解空间是一颗树的

Greedy并非完全不用考虑前面的过程，但是自底向上，Greedy知道最优的路径（这一步是最难证明的）

也就是Greedy知道怎么往上走，每一步只会考虑找出一个最优解，而不会像DP去维护每一步的多种可能性

相当于从最优路径出发，不断遍历/迭代/回溯/递归，最终完成整个原问题

应用场景：解决一个问题需要多个步骤，每一个步骤有多种选择。可以使用贪心算法解决的问题，每一步只需要解决一个子问题，只做出一种选择，就可以完成任务。

「回溯算法」需要记录每一个步骤、每一个选择，用于回答所有具体解的问题

「动态规划」需要记录的是每一个步骤、所有选择的汇总值（最大、最小或者计数）

「贪心算法」由于适用的问题，每一个步骤只有一种选择，且一般只需要记录与当前步骤相关的变量的值。

动态规划：从所有子问题的解中找出最优解，正向寻找；DP需要考虑所有子问题

贪心：找到最优路径，回溯原问题，逆向寻找；贪心只用每次考虑当前问题，通常自底向上

最优子结构：规模较大的问题的解由规模较小的子问题的解组成

区别于DP，可以使用「贪心算法」的问题「规模较大的问题的解」只由其中一个「规模较小的子问题的解」决定；而DP因为具有多种选择，所以不确定由哪个转移来

无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；

贪心选择性质：从局部最优解可以得到全局最优解。

能用Greedy的条件：最优子结构、无后效性、全局最优解能用DP的条件：最优子结构、无后效性

能用Greedy解的==能用DP解能用DP解的!=能用Greedy解

贪心问题相比于动态规划更难的是证明，或者说证明之于贪心就像更新公式之于DP。

常见问题

找零钱问题

区间选择问题

跳跃问题

最长递增子序列

选竟可能小的数

我们来选首个区间

因为把左边当作没有其他元素，所以只用考虑右端点的位置（更左的可能没有帮助，但是有更好的潜力）

选完最左边的右端点后，后面成了一个子问题

首先目的是尽可能少地移除区间，一个简单的想法便是让我们剩余空间更大，换一种说法就是我们选择右边界更小的那个区间，如上例子，我们不会选择[1,4]区间，而是选择[1,2]区间，它保证了剩余空间更大。即在区间满足不冲突的条件下，贪心地使用右边界更小的区间。

果不选更小的，换而言之，更大右边界与相对较小的右边界之间就不能再存放其他区间了，如[1,4][1,2]中选择[1,4]就导致原本[2,4]区间不能再存放其他东西了，因此取更大的右边界值并不能使得我们最终移除的区间更少

贪心 + 二分查找

更新操作：具体怎么更新先不管，可能n可能1，另外还可能不做

~~更新前面，可能对结果没影响；不过这确确实实维护了最优子结构~~

len是ans

435. 无重叠区间

贪心 + 遍历

贪心算法求的是限制条件增多（但能满足原始条件）下的一个特殊解。贪的并不是解的数量，相反，它通过增加限制条件，减少要考虑到的可能解。而动态规划问题里，会通过一个“缓存器”一样的部件存储已解的子问题的解，进而拿这个缓存器里的内容继续向后求解父问题的解。

贪心实际上就是子问题最优解，在这道题中贪在于每次寻找最左右边界即是扎爆气球个数最多的选项这就是当前子问题的最优解，所以贪心问题的关键的关键就是寻找子问题最优解

活动时间安排

经常最小右边界

对于不同的目标「贪心算法」贪心的点是不一样的。

「贪心算法」充分挖掘了问题本身的特点，少考虑了很多动态规划需要考虑的子问题。也就是说，「贪心算法」的应用与问题的场景密切相关。

(一堆跳跃游戏）

（贪心题库）

int r=curIdx+1;

别用++，那把东西改掉了