贪心前言
介绍一下我所知的贪心吧。
贪心,是一种非常灵活的算法,因此也有了极高的难度。
它往往是通过一些方式将局部最优决策聚集或连续选取来得到全局最优解并降低时间复杂度。
贪心题还考察了你对状态的简化,如将圆形覆盖线段转化为线段覆盖问题。
贪心题有以下常用的思考技巧:
1.邻项交换
2.范围缩放
3.决策包容性
4.反证法
5.数学归纳法
用线段覆盖问题来举个例,
我们对线段按右端点排序,然后从右往左贪心地选取即可,那我们是怎么想到要排序的?是这样的,其实线段覆盖问题可以看作一类偏序问题,排序是确定顺序的一种好方法,所以想到了。
当然,邻项交换的本质是冒泡排序,本身就是在将其它问题化作偏序问题后解决,所以不论是简单的一维偏序还是高维偏序都有可以贪心的地方。
但是时刻注意,贪心是最优化算法,找到并交换逆序对的目的是重叠最优解,换句话说,只要有逆序,就有优化解的可能。
注意我们要选的是合法情况下最往左的值,可以用其它数据结构优化。
在我看来,比起说贪心更需要灵感,更应该说贪心更需要学会去剪去 无用信息,去找到 产生后效性 的信息,然后设计策略将这些多维信息都涵盖进去。
我们可以用之前提到的方法去证明。
当然,这种涵盖是有实际意义的,比如说国王游戏这题,对于最后一个人他左手的乘积是固定的,此时如果右手的除数更大,则答案会更优,对于前面那一个人,如果后面哪一个人自己的乘积越大,那前面哪一个贡献就会更小。
当然实际思考应该是,找到前后两个人,比较他们交换或不交换的贡献和,然后化简,剩下的形式就是交换依据。
除此之外,还有 反悔贪心 和 反悔自动机,它们是多维偏序贪心问题的极简便的做法。
但还有一些问题,比如回文,这种题用排序的方式解决不了, 正确的方式是找到它的当前局部决策,用贪心的思想选最优的。
这类问题的难点在于贪心策略和将其转化为贪心的构造。
比如说田忌赛马,因为只有送、打平、虐三种情况,通过贪心我们发现每次决策只用看最强和最弱两匹马。
如果最强马能赢,就不用冒输的风险用其它马,这是个逻辑链。
如果小于,就直接用最弱马来对掉对方最强马,如果等于,就要看最弱马,因为有败一场、胜一场,平了两种可能最优解,自己讨论。
值得注意的是我们每次只决一次胜负,因为没必要将最强马和对方的最强或最弱马早早对掉。
本分享部分用词属于原创,大部分思考方式略显清奇,酌情观看
喜欢可以点个关注。