近期学了贪心,遇到一些问题,主要是两个方面。
一、贪心策略错误
经常遇到一道贪心题,需要排序,用了错误的排序策略。因为证明一个策略的正确性通常比较困难,而推出一个正确的策略是更难的。
我一般采用蒙结论再用小数据验证,但会存在只要贪心策略复杂一点我就蒙不出来,有什么好的方法能够像数学推式子一样有保障地推出大部分贪心题地贪心策略?
二、看不出一道题是贪心题
以前我把每道跟最优化有关的非计数题都看作贪心,后来改掉这个习惯,导致会把贪心题当成 DP,网络流等等其它算法,然后只能得部分分或者超时。
所以如何才能快速判断一道题是否可以用贪心求解?
求解答,谢谢。