在我們正式開始之前，我想說幾句題外話:
我知道貪婪算法對很多學生來說有點難。難的不是對概念的理解，而是壹看就會做，然後壹旦做了就會放棄，然後半途而廢。
我想說這很正常，因為貪婪算法是壹種算法思想，但沒有套路可談，不像我們上次研究二叉樹時，解題是遞歸+叠代，可以從上到下、從下到上、從左到右集成，套路很明顯。
不用說，當談到動態規劃時，更容易區分貪婪算法和動態規劃。
遇到這些問題該怎麽辦？說幹就幹，做題+總結就行。
貪婪算法
要學習貪婪算法，我們必須首先了解它的概念。
貪婪算法是指從問題的初始狀態開始，在每壹步中采取最佳或最優（最有利）的選擇，從而獲得結果的最優值（或更好的值）。
通過這個概念，我們可以知道貪婪算法的兩個關鍵點:
貪婪算法在解決問題時總是做出最佳選擇。
貪心算法得到的結果不壹定是最優結果，但絕對是比較接近最優解的結果。
看來這兩點可能很難理解。我將用兩個例子來理解。
例1:我們現在有四種硬幣，即20、10、5和1。如果我想湊足36元，我至少需要多少硬幣？
根據貪婪算法，我們上來的時候肯定需要幾張20。這個問題需要1，還剩下36-20 = 16。
看完20，我們再來看10元，這需要1塊10元，現在有16-10 = 6。
接下來看5和1，分別需要1。
最後，我們得到的答案是，如果我們要收集36元，我們至少需要4張鈔票。
在本例中，每次都使用最大的鈔票進行匹配，剩余的余額與較小的面額進行匹配。這是我們在1點說的。解決問題時，我們總是做出目前最好的選擇。
例2:讓我們以硬幣散落為例。現在我們有三種硬幣:10、9和1。如果我們要收集18元，至少需要多少枚硬幣？
在這個例子中，如果我們仍然使用上面的貪婪策略，那就完了。
上來壹看需要10元，所以這題需要1，剩余金額8元，所以不能用9註，只能用8註1元，所以最後結果是我用了9註。
而且通過小學知識，我們可以肉眼看到使用兩張9元紙幣是可以的。
這個例子說明了第二點:貪婪算法得到的結果不壹定是最優結。
看看這是不是很蠢？犯傻是對的。
妳現在應該記住壹件事:貪婪算法只在某些情況下有用。至於什麽是部分情況，這取決於多做題。
嘿，嘿，先別動手，然後看看，比如上面兩個例子，妳應該看看數字之間的規律。在示例1中，硬幣互為倍數，但在示例2中，沒有規律。
這得通過多做題多總結來實現。
什麽時候使用貪婪？
說實話，這就是貪婪算法對我們來說“困難”的地方，也就是說，沒有任何建模可以直接告訴我們“這就是貪婪。”
如果我們堅持的話，它們大多用於像上壹節中給出的例子那樣的組合優化問題，並且解決它們的過程涉及多步判斷。
當妳遇到這樣的問題時，妳的想法可以依靠貪婪算法，但它只是“可以”。
因為妳看到這樣壹個問題，當妳想到壹個貪婪算法時，妳必須首先自己想出壹個貪婪策略，然後妳必須驗證妳使用的貪婪策略產生的結果是否是最優的。如果沒有，您可能需要使用我們將在下壹個項目中學習的動態編程。
大家大概都會問怎麽驗證，隨便舉幾個靠譜的例子驗證壹下。
當然，我這裏說的是“可靠”，這只是壹些特例。否則，如果妳隨便舉幾個例子，發現它們是對的，妳就會覺得此時妳正在做的事情是對的，可能只是妳舉的這些例子剛剛好。
我想在這裏多說幾句:
事實上，通常來說，驗證像這樣的貪婪算法的正確性的最可靠的方法是通過數學推導，例如數學歸納法和逆方法。
但是怎麽說呢？雖然數學推導是正確的，結果是正確的，但這對我們來說是完全沒有必要的，更不用說很多人根本無法推導出來。即使他們知道，對我們來說也沒什麽意義。畢竟目的不同，所以才會走得遠。
從我們的角度來看，我們可以通過引用壹些特殊案例來完全驗證大多數問題。
當然，如果妳要問我如何舉特例，我只能告訴妳:多做題就好。
貪心法求解步驟。
貪婪算法的解題步驟實際上與分治算法非常相似。
之前講分治算法的時候，講了分治算法的三個步驟:
Divide:將原問題分成更小的子問題，這些子問題彼此獨立，並且具有與原問題相同的形式。
分治後遞歸求解子問題。
合並:這壹步不是必需的。有些問題涉及合並子問題的解，以及將子問題的解合並到原問題的解中。有些問題不需要，只要找到子問題的解就可以了。
貪婪算法的步驟是相似的。如果妳確定貪婪算法是可解的，也有三個步驟:
（1）將問題分解成多個子問題。
（2）選擇合適的貪婪策略，得到每個子問題的局部最優解。
（3）將子問題的局部最優解合並為原問題的最優解。
妳認為這樣很簡單嗎？嘿，嘿，嘿，當妳做題時，妳會知道有時妳看到的並不是真實的感覺。
貪婪算法的內容到此為止。理論上的東西真的不多。看完之後只是給妳壹個印象。
只要妳知道理論上的東西，妳就別無選擇，只能好好學習貪婪。多做題多練習就好了，多看多感受。
其實壹系列的動作就是:誒，這個問題好像比較貪心，試試吧，得到壹個結果，找幾個特例來測試壹下，如果是最優解，壹切都會好的，不是最優解，那就想想是不是可以用動態規劃什麽的來解決。
最後，不必對貪婪算法感到恐慌。退壹萬步講，就算學不好，問題也不大。壹般面試中貪心的測試比較少。