[[433278]]

貪心力扣題目分類大綱如下，可以幫助大家在刷題的時候?qū)ω澬乃惴ㄓ幸粋€整體性的把握。

什么是貪心

貪心的本質(zhì)是選擇每一階段的局部最優(yōu)，從而達到全局最優(yōu)。

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

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

指定每次拿最大的，最終結(jié)果就是拿走最大數(shù)額的錢。

每次拿最大的就是局部最優(yōu)，最后拿走最大數(shù)額的錢就是推出全局最優(yōu)。

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

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

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

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

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

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

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

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

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

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

一般數(shù)學(xué)證明有如下兩種方法：

• 數(shù)學(xué)歸納法
• 反證法

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

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

舉一個不太恰當(dāng)?shù)睦樱何乙靡幌?+1 = 2，但我要先證明1+1 為什么等于2。嚴謹是嚴謹了，但沒必要。

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

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

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

那么刷題的時候什么時候真的需要數(shù)學(xué)推導(dǎo)呢?

例如這道題目：鏈表：環(huán)找到了，那入口呢?，這道題不用數(shù)學(xué)推導(dǎo)一下，就找不出環(huán)的起始位置，想試一下就不知道怎么試，這種題目確實需要數(shù)學(xué)簡單推導(dǎo)一下。

貪心一般解題步驟

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

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

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

總結(jié)

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

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

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

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