贪心综述

作者:江月迟迟

发表于:2024-12-10

字数统计:312 字

预计阅读2分钟

贪心就是将大问题分解成子问题，寻找众子问题的最优解，叠加就是大问题的最优解。有以下几个特征：

1. 大问题可分解。
2. 子问题最优解有解。
3. 子问题可以合并成大问题。

贪心是一种思想。那么我们解题也遵循这个思考模板。

1. 拆分大问题。
2. 解决子问题最优解。
3. 叠加子问题最优解。

依旧拆解这部分模板。

1. 拆分大问题，需要知道大问题是什么，怎么样拆分。一个单调递增的数组，可以拆解成每一小组的后一个比前一个要大；一个摆动数列，拆分成先是后一个比前一个大/小，然后后一个又比前一个小/大。
2. 解决子问题最优解，往往涉及到几种情况，注意不同情况的处理，注意边界问题。
3. 叠加子问题最优解，有的时候大问题是一个数组，从前往后和从后往前一样，有的时候则不一样，子问题的叠加可能是有方向的，在合并的时候需要注意。