最小堆的貪心演算法

A. 貪心演算法總結

做了這10道題，其實發現貪心演算法沒有什麼規律，要說有什麼共同特點就是都是由局部最優從而推出全局最優，每個題基本上都要考慮其局部最優是什麼，其全局最優是什麼，所以雖然都用到了貪心演算法的思想，但是題與題之間又沒有什麼規律可言。

現在把這10道題的思路總結一下（總結主要以我的主觀看法在寫，可能別人看會不知道我在說什麼）

1.分發餅干：

https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

思路：想要完成最多的小孩滿足，那麼就得最小的餅干給胃口最小的小孩

這里的貪心思想，

局部最優就是盡可能讓一個餅干喂飽一個

全局最優就是最多的小孩滿足

2.擺動序列：

https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html

思路：這里要找到最長的擺動序列，那麼其實就是找那些波峰波谷，如圖所示

可以看出來，在到達波峰波谷的路上有幾個數字不會影響什麼，可以直接去掉。

那麼這里的局部最優就是把單調坡上的點刪掉，保留最多的波峰波谷

全局最優就是得到對多的波峰波谷，即最長的擺動序列

3.最大子序和

https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html

這道題顯然可以暴力解出來，即列出所有子序和，找出最大的，不過計算量會比貪心大很多。

這里主要介紹貪心解的思想：

想要得到最大子序和，就得保證每次相加時，相加後不能為負數，因為負數繼續往下加一定是拉低總和的，那麼我們當加成到負數時就重新從下個數開始加，並實時記錄最大的子序和，這樣一遍循環就能得出最大子序和。

局部最優：加成負數就立刻停止，並從下個元素重新開始

全局最優：得到最大子序和

4.買賣股票的最佳時機II

https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html

思路：想要得到最大利潤，那就要低價買入高價賣出，那麼怎樣的買賣才能得到最大利潤呢。

這里就體現出貪心演算法的「貪」字（我猜的），這道題貪在哪呢，貪在只要有利可圖就去做，即只要今天買入的價錢比明天賣出的價錢底，即有利可圖，那麼我就去做，做就是在今天買入，在明天賣出。

局部最優：得到每天的最大正利潤

全局最優：得到最大利潤

5.跳躍游戲

https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html

思路：每個數組的元素代表的是可以跳的最遠下標，那麼我們只要使那個最遠下標包含最後一個下標就是可以跳到，那麼我們每跳到一個位置就要更新那個可以跳的范圍，即可以跳到的最遠下標。

局部最優：每次跳躍都得出最遠的跳躍范圍

全局最優：最後能跳到的最大范圍

6.跳躍游戲II

https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html

思路：這道題要得到最小的跳躍數，其實只要保證跳的是位置是可以跳范圍內更新最遠范圍的位置就可以了。

為什麼這么說呢？以題例來說：

我們剛開始在『0』的位置，我們能跳到『1』和『2』的位置，那麼我們怎麼跳呢？可以看到跳到『1』之後更新的最大范圍是『4』，跳到『2』之後更新的最大范圍是『3』，所以我們就跳『2』了，因為跳『1』之後更新的最大可跳范圍更大包含了跳『2』的最大可跳范圍，那麼肯定是跳『3』最優呀，這里就體現了局部最優的思想。

局部最優：每次跳後，更新的最大可調范圍最大

全局最優：跳躍次數最少

7.K次取反後最大化的數組和

https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html

思路：想要得到最大數組和，我們就可以想到怎樣做呢？

一，盡可能保證負數最少

二，負數絕對值大的優先變正

三，正數絕對值小的優先變負，有零變零

本著這三條原則做，就能做出來。

那麼這道題體現了什麼貪心思想呢？

我感覺，前面那三條都是貪心中『貪』的體現

在負數中，局部最優就是：絕對值大的負數優先變正

在正數中，局部最優就是：絕對值小的正數變負，有零變零

得到的全局最優：數組和最大

8.加油站

https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html

思路：首先可以想到這道題是可以暴力解出來了，即分別以每個加油站為起點，得出可以跑一圈的加油站

那麼貪心思想做，該怎麼做呢，首先可以想到，如果以一個1點為起點當跑著跑著跑到3，油變為負數時，那麼說明以這個起點是不行的，但是以2或3為起點行不行呢？答案肯定是不行的，因為1跑到3，油變為負，說明1~3的gas=0的，所以可以得出，如果1~3油數變為負數，那麼由2~3油數肯定也為負數。

所以這里就可以得出，如果經過幾個加油站油數變為負了，那麼起點就更新為這一段路的下個加油站跑

局部最優：油量一旦為負，就從下個加油站重新跑

全局最優：得出可以跑一圈的加油站起點

9.分發糖果

https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

思路：每個孩子至少一個，如果一個孩子比他旁邊的孩子優秀，就要比他旁邊的糖果多，這道題一旦兩邊都考慮很容易顧此失彼，所以我們就定義兩個循環，分別從左到右，從右到左去考慮，只要更優秀則比他旁邊的多1，如果已經多了就不用變了。

局部最優：保證優秀的孩子比他旁邊的孩子糖果多

全局最優：滿足題中條件，至少要發的糖果

10.檸檬水找零

https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

思路：我們在找零時要遵守的規則一定是：

5 得5

10 得10減5

15 得15，優先減一個10減一個5  如果10塊沒有則減三個5

局部最優：以最少用的5塊的方式找零

全局最優：得到找零能否進行下去

B. 五大常用演算法之一：貪心演算法

所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，換句話說，當考慮做何種選擇的時候，我們只考慮對當前問題最佳的選擇而不考慮子問題的結果。這是貪心演算法可行的第一個基本要素。貪心演算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。 對於一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。
當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用貪心演算法求解的關鍵特徵。

值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。比如， 求最小生成樹的Prim演算法和Kruskal演算法都是漂亮的貪心演算法 。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
貪心策略：選取價值最大者。反例：

W=30

物品：A B C

重量：28 12 12

價值：30 20 20

根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。

（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。

（3）貪心策略：選取單位重量價值最大的物品。反例：

W=30

物品：A B C

重量：28 20 10

價值：28 20 10

根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。但是果在條件中加一句當遇見單位價值相同的時候,優先裝重量小的,這樣的問題就可以解決.

所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。（因為這一類演算法普及性不高，而且技術含量是非常高的，需要通過一些反例確定隨機的對象是什麼，隨機程度如何，但也是不能保證完全正確，只能是極大的幾率正確）。

C. 演算法09-貪心演算法

貪心演算法與動態規劃的不同在於它對每個子問題的解決方案都作出選擇，不能回退。動態規劃則會保存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能。

很多情況下，可以在某一步用貪心演算法，全局再加一個搜索或遞歸或動態規劃之類

貪心法可以解決一些最優化問題，如:求圖中的最小生成樹、求哈夫曼編碼等。然而對於工程和生活中的問題，貪心法一般不能得到我們所要求的答案。
一單一個問題可以通過貪心法來解決，那麼貪心法一般是解決這個問題的最好辦法。由於貪心法的高效性以及其所求得的答案比較接近最優結果，貪心法也可以用作輔助演算法或者直接解決一些要求結果不特別精確的問題。

當硬幣可選集合固定:Coins = [20,10,5,1],求最少幾個硬幣可以拼出總數。比如total=36。
36 - 20 = 16 20
16 - 10 = 6 20 10
6 - 5 = 1 20 10 5
1 - 1 = 0 20 10 5 1
前面這些硬幣依次是後面硬幣的整數倍，可以用貪心法，能得到最優解，

貪心法的反例
非整除關系的硬幣，可選集合:Coins = [10,9,1],求拼出總數為18最少需要幾個硬幣？
最優化演算法:9 + 9 = 18 兩個9
貪心演算法:18 - 10 = 8 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 0 八個1

簡單地說，問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。這種子問題最優解成為最優子結構。
貪心演算法與動態規劃的不同在於它對每個子問題的最終方案都作出選擇，不能回退。
動態規劃則會保存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能。

假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多隻能給一塊餅干。
對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅乾的最小尺寸；並且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，並輸出這個最大數值。
示例 1:
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由於他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應該輸出1。
示例 2:
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數量和尺寸都足以讓所有孩子滿足。
所以你應該輸出2.
提示：
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個演算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
隨後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之後再將它們賣出。
因為這樣屬於同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

給定一個非負整數數組 nums ，你最初位於數組的 第一個下標 。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達最後一個下標。
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然後再從下標 1 跳 3 步到達最後一個下標。
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最後一個下標。

給定一個非負整數數組，你最初位於數組的第一個位置。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目標是使用最少的跳躍次數到達數組的最後一個位置。
示例:
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最後一個位置的最小跳躍數是 2。
從下標為 0 跳到下標為 1 的位置，跳 1 步，然後跳 3 步到達數組的最後一個位置。
說明:
假設你總是可以到達數組的最後一個位置。
移動下標只要遇到當前覆蓋最遠距離的下標，直接步數加一，不考慮是不是終點的情況。
想要達到這樣的效果，只要讓移動下標，最大隻能移動到nums.size - 2的地方就可以了。
因為當移動下標指向nums.size - 2時：
如果移動下標等於當前覆蓋最大距離下標， 需要再走一步（即ans++），因為最後一步一定是可以到的終點。（題目假設總是可以到達數組的最後一個位置），如圖：

如果移動下標不等於當前覆蓋最大距離下標，說明當前覆蓋最遠距離就可以直接達到終點了，不需要再走一步。如圖：

機器人在一個無限大小的 XY 網格平面上行走，從點 (0, 0) 處開始出發，面向北方。該機器人可以接收以下三種類型的命令 commands ：
-2 ：向左轉 90 度
-1 ：向右轉 90 度
1 <= x <= 9 ：向前移動 x 個單位長度
在網格上有一些格子被視為障礙物 obstacles 。第 i 個障礙物位於網格點 obstacles[i] = (xi, yi) 。
機器人無法走到障礙物上，它將會停留在障礙物的前一個網格方塊上，但仍然可以繼續嘗試進行該路線的其餘部分。
返回從原點到機器人所有經過的路徑點（坐標為整數）的最大歐式距離的平方。（即，如果距離為 5 ，則返回 25 ）
注意：
北表示 +Y 方向。
東表示 +X 方向。
南表示 -Y 方向。
西表示 -X 方向。
示例 1：
輸入：commands = [4,-1,3], obstacles = []
輸出：25
解釋：
機器人開始位於 (0, 0)：

在檸檬水攤上，每一杯檸檬水的售價為 5 美元。
顧客排隊購買你的產品，（按賬單 bills 支付的順序）一次購買一杯。
每位顧客只買一杯檸檬水，然後向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元。
注意，一開始你手頭沒有任何零錢。
如果你能給每位顧客正確找零，返回 true ，否則返回 false 。
示例 1：
輸入：[5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那裡，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那裡，我們收取一張 10 美元的鈔票，並返還 5 美元。
第 5 位顧客那裡，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由於所有客戶都得到了正確的找零，所以我們輸出 true。
示例 2：
輸入：[5,5,10]
輸出：true
示例 3：
輸入：[10,10]
輸出：false
示例 4：
輸入：[5,5,10,10,20]
輸出：false
解釋：
前 2 位顧客那裡，我們按順序收取 2 張 5 美元的鈔票。
對於接下來的 2 位顧客，我們收取一張 10 美元的鈔票，然後返還 5 美元。
對於最後一位顧客，我們無法退回 15 美元，因為我們現在只有兩張 10 美元的鈔票。
由於不是每位顧客都得到了正確的找零，所以答案是 false。

給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。
你可以認為每種硬幣的數量是無限的。
示例 1：
輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1
示例 2：
輸入：coins = [2], amount = 3
輸出：-1
示例 3：
輸入：coins = [1], amount = 0
輸出：0
示例 4：
輸入：coins = [1], amount = 1
輸出：1
示例 5：
輸入：coins = [1], amount = 2
輸出：2

D. 哈夫曼編碼（貪心演算法）

參考： 哈夫曼編碼

哈夫曼編碼是一種十分有效的編碼方法，廣泛應用於 數據壓縮 中
通過採用 不等長 的編碼方式，根據 字元頻率的不同 ，選擇 不同長度的編碼 ，對頻率 越高 的字元採用 越短 的編碼實現數據的高度壓縮。
這種對頻率越高的字元採用越短的編碼來編碼的方式應用的就是貪心演算法的思想。

下面看一個例子：
假如我們有一個包含1000個字元的文件，每個字元佔1個byte(1byte=8bits)，則存儲這100個字元一共需要8000bits。這還是有一些大的
那我們統計一下這1000個字元中總共有多少種字元，原來需要8bit來表示一個字元，如果使用更少的位數來表示這些字元，則可以減少存儲空間。
假設這1000個字元中總共有a、b、c、d、e、f共6種字元，使用使用3個二進制位來表示的話，存儲這1000個字元就只需要3000bits，比原來更節省存儲空間。

或許還可以再壓縮一下：
根據字元出現的 頻率 給與字元 不等長 的編碼，頻率越高的字元編碼越短，頻率越低的字元編碼越長。
它不能像等長編碼一樣直接按固定長度去讀取二進制位，翻譯成字元，為了能夠准確讀取翻譯字元，它要求一個字元的編碼不能是另外一個字元的前綴。

假設a、b、c、d、e、f這6個字元出現的頻率依次降低，則我們可以給與他們這樣的編碼

假如字元的出現頻率如圖所示，按照這樣的編碼表示的話，總位數如圖，一共2100bits，更加節省空間了

貪心策略：頻率小的字元，優先入隊。

步驟：
1.將每一個字元作為節點，以出現頻率大小作為權重，將其都放入 優先隊列 中（一個最小堆）；
2.每次出隊兩個節點並創建一個父節點，使其權值為剛剛出隊的節點的權值和，並且為兩個節點的父節點（合並）。然後將這個樹入隊。
3.重復操作2，直到隊列中只有一個元素（此時這個元素表示形式應該為一個樹）時，完成創建。

創建好了樹，該怎麼編碼呢？
我們對一個哈夫曼樹，從父節點開始的所有節點，往左邊標0，右邊標1。那麼到達葉子節點的順次編碼就可以找到了。

C：字元集合
Q：優先隊列
EXTRACT-MIN：傳入一個隊列，出隊最小的元素
INSERT：將z插入到Q中

當for循環結束之後，此時隊列中只有一個元素，就是我們需要的哈夫曼樹，最後返回此樹即可。

假設T樹已經是一個最優的樹，假設x、y的頻率小於等於最低處的a、b，然後交換x、a，y、b。

計算代價是否發生變化。
比如這里比較 T 變成 T 』 後代價是否變化，發現代價變小或不變。

同理T』到T』』，又因為T本來假設就是最優的，所以只能相等
所以T』』也應該符合條件，即貪婪演算法，每次取最小的兩個節點出來這種做法是正確的

E. (三) 貪心演算法

貪心演算法的思想非常簡單且演算法效率很高，在一些問題的解決上有著明顯的優勢。

假設有3種硬幣，面值分別為1元、5角、1角。這3種硬幣各自的數量不限，現在要找給顧客3元6角錢，請問怎樣找才能使得找給顧客的硬幣數量最少呢？

你也許會不假思索的說出答案：找給顧客3枚1元硬幣，1枚5角硬幣，1枚1角硬幣。其實也可以找給顧客7枚5角硬幣，1枚1角硬幣。可是在這里不符合題意。在這里，我們下意識地應用了所謂貪心演算法解決這個問題。

所謂貪心演算法，就是 總是做出在當前看來是最好的選擇(未從整體考慮) 的一種方法。以上述的題目為例，為了找給顧客的硬幣數量最少，在選擇硬幣的面值時，當然是盡可能地選擇面值大的硬幣。因此，下意識地遵循了以下方案：
（1）首先找出一個面值不超過3元6角的最大硬幣，即1元硬幣。
（2）然後從3元6角中減去1元，得到2元6角，再找出一個面值不超過2元6角的最大硬幣，即1元硬幣。
（3）然後從2元6角中減去1元，得到1元6角，再找出一個面值不超過1元6角的最大硬幣，即1元硬幣。
（4）然後從1元6角中減去1元，得到6角，再找出一個面值不超過6角的最大硬幣，即5角硬幣。
（5）然後從6角中減去5角，得到1角，再找出一個面值不超過1角的最大硬幣，即1角硬幣。
（6）找零錢的過程結束。
這個過程就是一個典型的貪心演算法思想。

貪心策略總是做出在當前看來是最優的選擇，也就是說貪心策略並不是從整體上加以考慮，它所做出的選擇只是在某種意義上的 局部最優解 ，而許多問題自身的特性決定了該問題運用貪心策略可以得到最優解或較優解。(註：貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題它能產生整體最優解。但其解必然是最優解的很好近似解。）

貪心演算法沒有固定的演算法框架，演算法設計的關鍵是 貪心策略的選擇 。選擇的貪心策略必須具備無後效性。

貪心策略 適用的前提 是：

嚴格意義上講，要使用貪心演算法求解問題，該問題應當具備以下性質：

注意 ：對於一個給定的問題，往往可能有好幾種量度標准。初看起來，這些量度標准似乎都是可取的，但實際上，用其中的大多數量度標准作貪婪處理所得到該量度意義下的最優解並不是問題的最優解，而是次優解。

因此， 選擇能產生問題最優解的最優量度標準是使用貪婪演算法的核心 。

實際上，貪心演算法 適用的情況很少 。一般，對一個問題分析是否適用於貪心演算法，可以先選擇該問題下的幾個實際數據進行分析，就可做出判斷。

最優解問題大部分都可以拆分成一個個的子問題(多階段決策問題)，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。

貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。

動態規劃方法代表了這一類問題的一般解法， 自底向上 構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。

而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始( 自頂向下 )，選擇最優的路，一直走到底就可以了。

一個問題分為多個階段，每個階段可以有n種決策，各個階段的決策構成一個決策序列，稱為一個策略。
這兩種演算法都是選擇性演算法，在進行決策的選擇時：

前提是這個問題得具有貪心選擇性質，需要證明(數學歸納法(第一、第二))，如果不滿足那就只能使用動態規劃解決。(一旦證明貪心選擇性質，用貪心演算法解決問題比動態規劃具有更低的時間復雜度和空間復雜度。)

從范疇上來看：
Greedy ⊂ DP ⊂ Searching （貪心是動規的特例）
即所有的貪心演算法問題都能用DP求解，更可以歸結為一個搜索問題，反之不成立。

貪心演算法所作的選擇可以依賴於以往所作過的選擇，但決不依賴於將來的選擇，也不依賴於子問題的解，這使得演算法在編碼和執行的過程中都有著一定的速度優勢。如果一個問題可以同時用幾種方法解決，貪心演算法應該是最好的選擇之一。但是貪心演算法並不是對所有的問題都能得到整體最優解或最理想的近似解，與回溯法等比較，它的適用區域相對狹窄許多，因此正確地判斷它的應用時機十分重要。

一步一步地進行，常 以當前情況為基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況 ，它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。

它採用 自頂向下 ，以 迭代 的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以 貪心法不需要回溯 。

【問題描述】
馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條最短路徑。

【貪心演算法】
其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。

F. 程序員演算法基礎——貪心演算法

貪心是人類自帶的能力，貪心演算法是在貪心決策上進行統籌規劃的統稱。

比如一道常見的演算法筆試題---- 跳一跳 ：

我們自然而然能產生一種解法：盡可能的往右跳，看最後是否能到達。
本文即是對這種貪心決策的介紹。

狹義的貪心演算法指的是解最優化問題的一種特殊方法，解決過程中總是做出當下最好的選擇，因為具有最優子結構的特點，局部最優解可以得到全局最優解；這種貪心演算法是動態規劃的一種特例。 能用貪心解決的問題，也可以用動態規劃解決。

而廣義的貪心指的是一種通用的貪心策略，基於當前局面而進行貪心決策。以 跳一跳 的題目為例：
我們發現的題目的核心在於 向右能到達的最遠距離 ，我們用maxRight來表示；
此時有一種貪心的策略：從第1個盒子開始向右遍歷，對於每個經過的盒子，不斷更新maxRight的值。

貪心的思考過程類似動態規劃，依舊是兩步： 大事化小 ， 小事化了 。
大事化小：
一個較大的問題，通過找到與子問題的重疊，把復雜的問題劃分為多個小問題；
小事化了：
從小問題找到決策的核心，確定一種得到最優解的策略，比如跳一跳中的 向右能到達的最遠距離 ；

在證明局部的最優解是否可以推出全局最優解的時候，常會用到數學的證明方式。

如果是動態規劃：
要湊出m元，必須先湊出m-1、m-2、m-5、m-10元，我們用dp[i]表示湊出i元的最少紙幣數；
有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1 ;
容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；
根據以上遞推方程和初始化信息，可以容易推出dp[1~m]的所有值。

似乎有些不對？ 平時我們找零錢有這么復雜嗎？
從貪心演算法角度出發，當m>10且我們有10元紙幣，我們優先使用10元紙幣，然後再是5元、2元、1元紙幣。
從日常生活的經驗知道，這么做是正確的，但是為什麼？

假如我們把題目變成這樣，原來的策略還能生效嗎？

接下來我們來分析這種策略：
已知對於m元紙幣，1，2，5元紙幣使用了a，b，c張，我們有a+2b+5c=m；
假設存在一種情況，1、2、5元紙幣使用數是x，y，z張，使用了更少的5元紙幣（z<c），且紙幣張數更少（x+y+z<a+b+c），即是用更少5元紙幣得到最優解。
我們令k=5*(c-z)，k元紙幣需要floor(k/2)張2元紙幣，k%2張1元紙幣；（因為如果有2張1元紙幣，可以使用1張2元紙幣來替代，故而1元紙幣只能是0張或者1張）
容易知道，減少(c-z)張5元紙幣，需要增加floor(5*(c-z)/2)張2元紙幣和(5*(c-z))%2張紙幣，而這使得x+y+z必然大於a+b+c。
由此我們知道不可能存在使用更少5元紙幣的更優解。
所以優先使用大額紙幣是一種正確的貪心選擇。

對於1、5、7元紙幣，比如說要湊出10元，如果優先使用7元紙幣，則張數是4；（1+1+1+7）
但如果只使用5元紙幣，則張數是2；（5+5）
在這種情況下，優先使用大額紙幣是不正確的貪心選擇。（但用動態規劃仍能得到最優解）

如果是動態規劃：
前i秒的完成的任務數，可以由前面1~i-1秒的任務完成數推過來。
我們用 dp[i]表示前i秒能完成的任務數 ；
在計算前i秒能完成的任務數時，對於第j個任務，我們有兩種決策：
1、不執行這個任務，那麼dp[i]沒有變化；
2、執行這個任務，那麼必須騰出來(Sj, Tj)這段時間，那麼 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；
比如說對於任務j如果是第5秒開始第10秒結束，如果i>=10，那麼有 dp[i]=max(dp[i], dp[5] + 1)； （相當於把第5秒到第i秒的時間分配給任務j）

再考慮貪心的策略，現實生活中人們是如何安排這種多任務的事情？我換一種描述方式：

我們自然而然會想到一個策略： 先把結束時間早的兼職給做了！
為什麼？
因為先做完這個結束時間早的，能留出更多的時間做其他兼職。
我們天生具備了這種優化決策的能力。

這是一道 LeetCode題目 。
這個題目不能直接用動態規劃去解，比如用dp[i]表示前i個人需要的最少糖果數。
因為（前i個人的最少糖果數）這種狀態表示會收到第i+1個人的影響，如果a[i]>a[i+1]，那麼第i個人應該比第i+1個人多。
即是 這種狀態表示不具備無後效性。

如果是我們分配糖果，我們應該怎麼分配？
答案是： 從分數最低的開始。
按照分數排序，從最低開始分，每次判斷是否比左右的分數高。
假設每個人分c[i]個糖果，那麼對於第i個人有 c[i]=max(c[i-1],c[c+1])+1 ; （c[i]默認為0，如果在計算i的時候,c[i-1]為0，表示i-1的分數比i高）
但是，這樣解決的時間復雜度為 O(NLogN) ，主要瓶頸是在排序。
如果提交，會得到 Time Limit Exceeded 的提示。

我們需要對貪心的策略進行優化：
我們把左右兩種情況分開看。
如果只考慮比左邊的人分數高時，容易得到策略：
從左到右遍歷，如果a[i]>a[i-1]，則有c[i]=c[i-1]+1；否則c[i]=1。

再考慮比右邊的人分數高時，此時我們要從數組的最右邊，向左開始遍歷：
如果a[i]>a[i+1], 則有c[i]=c[i+1]+1；否則c[i]不變；

這樣講過兩次遍歷，我們可以得到一個分配方案，並且時間復雜度是 O(N) 。

題目給出關鍵信息：1、兩個人過河，耗時為較長的時間；
還有隱藏的信息：2、兩個人過河後，需要有一個人把船開回去；
要保證總時間盡可能小，這里有兩個關鍵原則： 應該使得兩個人時間差盡可能小（減少浪費），同時船回去的時間也盡可能小（減少等待）。

先不考慮空船回來的情況，如果有無限多的船，那麼應該怎麼分配？
答案： 每次從剩下的人選擇耗時最長的人，再選擇與他耗時最接近的人。

再考慮只有一條船的情況，假設有A/B/C三個人，並且耗時A<B<C。
那麼最快的方案是：A+B去, A回；A+C去；總耗時是A+B+C。（因為A是最快的，讓其他人來回時間只會更長， 減少等待的原則 ）

如果有A/B/C/D四個人，且耗時A<B<C<D，這時有兩種方案：
1、最快的來回送人方式，A+B去；A回；A+C去，A回；A+D去； 總耗時是B+C+D+2A （減少等待原則）
2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；總耗時是 3B+D+A （減少浪費原則）
對比方案1、2的選擇，我們發現差別僅在A+C和2B；
為何方案1、2差別里沒有D？
因為D最終一定要過河，且耗時一定為D。

如果有A/B/C/D/E 5個人，且耗時A<B<C<D<E，這時如何抉擇？
仍是從最慢的E看。（參考我們無限多船的情況）
方案1，減少等待；先送E過去，然後接著考慮四個人的情況；
方案2，減少浪費；先送E/D過去，然後接著考慮A/B/C三個人的情況；（4人的時候的方案2）

到5個人的時候，我們已經明顯發了一個特點：問題是重復，且可以由子問題去解決。
根據5個人的情況，我們可以推出狀態轉移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根據我們考慮的1、2、3、4個人的情況，我們分別可以算出dp[i]的初始化值：
dp[1] = a[1];
dp[2] = a[2];
dp[3] = a[2]+a[1]+a[3];
dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);

由上述的狀態轉移方程和初始化值，我們可以推出dp[n]的值。

貪心的學習過程，就是對自己的思考進行優化。
是把握已有信息，進行最優化決策。
這里還有一些收集的 貪心練習題 ，可以實踐練習。
這里 還有在線分享，歡迎報名。

G. 貪心演算法

平面點集三角剖分的貪心演算法要求三角剖分後邊的總長度盡可能小。演算法的基本思想是將所有的兩點間距離從小到大排序，依次序每次取一條三角剖分的邊，直至達到要求的邊數。以下是兩種貪心演算法的主要步驟。

3.2.2.1 貪心演算法1

第一步:設置一個記錄三角剖分中邊的數組T。

第二步:計算點集S中所有點對之間的距離d(p_i，p_j)，1≤i，j≤n，i≠j，並且對距離從小到大進行排序，設為d₁，d₂，…，d_n(n-1)/2，相應的線段記為e₁，e₂，…，e_n(n-1)/2，將這些線段存儲在數組E中。

第三步:從線段集E中取出長度最短的邊e₁存到T中作為三角剖分的第一條邊，此時k=1。

第四步:依次從E中取出長度最短的邊e_k，與T中已有的邊進行求交運算，如果不相交則存到T中，並從E中刪除e_k。這一步運行到S中沒有邊為止，即至k=n(n-1)/2。

第五步:輸出T。

該演算法中，第二步需要計算n(n-1)/2次距離，另外距離排序需要O(n²lgn)次比較。T中元素隨第四步循環次數的增加而增加，因此向T中加入一條新邊所需要的判定兩條線段是否相交的次數也隨之增加。如果第四步的前3n-6次循環後已經構成點集的三角剖分，那麼第四步循環所需要的判定兩條線段是否相交的次數為

1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n³)

在常數時間內可以判定兩條線段是否相交，因此該演算法的時間復雜性為O(n³)。

3.2.2.2 貪心演算法2

第一步:求點集的凸殼，設凸殼頂點為p₁，p₂，…，p_m，凸殼的邊為e₁，e₂，…，e_m。並將凸殼頂點按順序連接成邊的e_i加入T(三角剖分的邊集合)，並且e_i的權值被賦為1。凸殼內點的集合為S₁={p_m+1，p_m+2，…，p_n}。

第二步:從內部點S₁中任取一點p_i，求與p_i距離最近的點p_j，將線段 存入T。

第三步:求與p_j距離最近的點(除點p_i外)，設為p_k，並將線段 加入T，並將這些邊的權值設為1，而w_ij、w_jk和w_ki的值加1，即為2。邊的權值為2則表示該邊為兩個三角形共有。

第五步:對權值為1的邊(除e₁，e₂，…，e_m外)的兩個端點分別求與其距離最近的點，並將其連線(得到新的三角形)加入T，新三角形邊的權值加1。

第六步:對權值為1的邊重復上一步，當一條邊被使用一次其權值增加1，直到所有邊的權值均為2為止(除e₁，e₂，…，e_m外)。

貪心演算法2中，第一步耗費O(nlgn);第二步需要計算n-1次距離與n-2次比較;第三步求p_k要計算n-2次的距離與n-3次比較;第四步要進行(n-3)×3次的距離計算及(n-4)×3次比較;第五步至多進行n-6次的距離計算與n-7次比較;第六步到第五步的循環次數不超過3n-9;因此整個貪心演算法2的時間復雜性為

O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n²)