[[433278]]

貪心力扣題目分類大綱如下，可以幫助大家在刷題的時候對貪心算法有一個整體性的把握。

什么是貪心

貪心的本質是選擇每一階段的局部最優，從而達到全局最優。

這么說有點抽象，來舉一個例子：

例如，有一堆鈔票，你可以拿走十張，如果想達到最大的金額，你要怎么拿?

指定每次拿最大的，最終結果就是拿走最大數額的錢。

每次拿最大的就是局部最優，最后拿走最大數額的錢就是推出全局最優。

再舉一個例子如果是 有一堆盒子，你有一個背包體積為n，如何把背包盡可能裝滿，如果還每次選最大的盒子，就不行了。這時候就需要動態規劃。動態規劃的問題在下一個系列會詳細講解。

貪心的套路(什么時候用貪心)

很多同學做貪心的題目的時候，想不出來是貪心，想知道有沒有什么套路可以一看就看出來是貪心。

說實話貪心算法并沒有固定的套路。

所以唯一的難點就是如何通過局部最優，推出整體最優。

那么如何能看出局部最優是否能推出整體最優呢?有沒有什么固定策略或者套路呢?

不好意思，也沒有! 靠自己手動模擬，如果模擬可行，就可以試一試貪心策略，如果不可行，可能需要動態規劃。

有同學問了如何驗證可不可以用貪心算法呢?

最好用的策略就是舉反例，如果想不到反例，那么就試一試貪心吧。

可有同學認為手動模擬，舉例子得出的結論不靠譜，想要嚴格的數學證明。

一般數學證明有如下兩種方法：

• 數學歸納法
• 反證法

看教課書上講解貪心可以是一堆公式，估計大家連看都不想看，所以數學證明就不在我要講解的范圍內了，大家感興趣可以自行查找資料。

面試中基本不會讓面試者現場證明貪心的合理性，代碼寫出來跑過測試用例即可，或者自己能自圓其說理由就行了。

舉一個不太恰當的例子：我要用一下1+1 = 2，但我要先證明1+1 為什么等于2。嚴謹是嚴謹了，但沒必要。

雖然這個例子很極端，但可以表達這么個意思：刷題或者面試的時候，手動模擬一下感覺可以局部最優推出整體最優，而且想不到反例，那么就試一試貪心。

例如剛剛舉的拿鈔票的例子，就是模擬一下每次拿做大的，最后就能拿到最多的錢，這還要數學證明的話，其實就不在算法面試的范圍內了，可以看看專業的數學書籍!

所以這也是為什么很多同學通過(accept)了貪心的題目，但都不知道自己用了貪心算法，因為貪心有時候就是常識性的推導，所以會認為本應該就這么做!

那么刷題的時候什么時候真的需要數學推導呢?

例如這道題目：鏈表：環找到了，那入口呢?，這道題不用數學推導一下，就找不出環的起始位置，想試一下就不知道怎么試，這種題目確實需要數學簡單推導一下。

貪心一般解題步驟

貪心算法一般分為如下四步：

• 將問題分解為若干個子問題
• 找出適合的貪心策略
• 求解每一個子問題的最優解
• 將局部最優解堆疊成全局最優解

其實這個分的有點細了，真正做題的時候很難分出這么詳細的解題步驟，可能就是因為貪心的題目往往還和其他方面的知識混在一起。

總結

本篇給出了什么是貪心以及大家關心的貪心算法固定套路。

不好意思了，貪心沒有套路，說白了就是常識性推導加上舉反例。

最后給出貪心的一般解題步驟，大家可以發現這個解題步驟也是比較抽象的，不像是二叉樹，回溯算法，給出了那么具體的解題套路和模板。 

本篇沒有配圖，其實可以找一些動漫周邊或者搞笑的圖配一配(符合大多數公眾號文章的作風)，但這不是我的風格，所以本篇文字描述足以!