前言

貪心是人類自帶的能力隧魄，貪心算法是在貪心決策上進行統(tǒng)籌規(guī)劃的統(tǒng)稱尊剔。

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

有n個盒子排成一行十减，每個盒子上面有一個數(shù)字a[i]宗弯，表示最多能向右跳a[i]個盒子痒玩；
小明站在左邊第一個盒子淳附，請問能否到達最右邊的盒子？
比如說：[1, 2, 3, 0, 4] 可以到達第5個盒子蠢古；
[3, 2, 1, 0, 4] 無法到達第5個盒子奴曙；

我們自然而然能產(chǎn)生一種解法：盡可能的往右跳，看最后是否能到達草讶。
本文即是對這種貪心決策的介紹洽糟。

正文

貪心算法基礎(chǔ)概念

狹義的貪心算法指的是解最優(yōu)化問題的一種特殊方法，解決過程中總是做出當(dāng)下最好的選擇堕战，因為具有最優(yōu)子結(jié)構(gòu)的特點坤溃，局部最優(yōu)解可以得到全局最優(yōu)解；這種貪心算法是動態(tài)規(guī)劃的一種特例嘱丢。能用貪心解決的問題薪介，也可以用動態(tài)規(guī)劃解決。

而廣義的貪心指的是一種通用的貪心策略屿讽，基于當(dāng)前局面而進行貪心決策昭灵。以跳一跳的題目為例：
我們發(fā)現(xiàn)的題目的核心在于向右能到達的最遠距離吠裆，我們用maxRight來表示；
此時有一種貪心的策略：從第1個盒子開始向右遍歷烂完，對于每個經(jīng)過的盒子试疙，不斷更新maxRight的值。

貪心算法的思考過程

貪心的思考過程類似動態(tài)規(guī)劃抠蚣，依舊是兩步：大事化小祝旷，小事化了。
大事化兴徽：
一個較大的問題怀跛，通過找到與子問題的重疊，把復(fù)雜的問題劃分為多個小問題柄冲；
小事化了：
從小問題找到?jīng)Q策的核心吻谋，確定一種得到最優(yōu)解的策略，比如跳一跳中的向右能到達的最遠距離现横；

在證明局部的最優(yōu)解是否可以推出全局最優(yōu)解的時候漓拾，常會用到數(shù)學(xué)的證明方式。

貪心算法的具體應(yīng)用

1戒祠、紙幣找零問題

有1元骇两、2元、5元姜盈、10元的紙幣分別有a[1], a[2], a[3], a[4]張低千，要用這些紙幣湊出m元，至少要用多少張紙幣馏颂？

如果是動態(tài)規(guī)劃：
要湊出m元示血，必須先湊出m-1、m-2饱亮、m-5矾芙、m-10元，我們用dp[i]表示湊出i元的最少紙幣數(shù)近上；
有 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剔宪；
根據(jù)以上遞推方程和初始化信息，可以容易推出dp[1~m]的所有值壹无。

似乎有些不對葱绒？平時我們找零錢有這么復(fù)雜嗎？
從貪心算法角度出發(fā)斗锭，當(dāng)m>10且我們有10元紙幣地淀，我們優(yōu)先使用10元紙幣，然后再是5元岖是、2元帮毁、1元紙幣实苞。
從日常生活的經(jīng)驗知道，這么做是正確的烈疚，但是為什么黔牵？

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

有1元猾浦、5元、7元的紙幣分別有a[1], a[2], a[3]張灯抛，要用這些紙幣湊出m元金赦，至少要用多少張紙幣？

接下來我們來分析這種策略：
已知對于m元紙幣对嚼，1夹抗，2，5元紙幣使用了a猪半，b兔朦，c張偷线，我們有a+2b+5c=m磨确；
假設(shè)存在一種情況，1声邦、2乏奥、5元紙幣使用數(shù)是x，y亥曹，z張邓了，使用了更少的5元紙幣（z<c），且紙幣張數(shù)更少（x+y+z<a+b+c）媳瞪，即是用更少5元紙幣得到最優(yōu)解骗炉。
我們令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元紙幣的更優(yōu)解。
所以優(yōu)先使用大額紙幣是一種正確的貪心選擇察蹲。

對于1请垛、5催训、7元紙幣，比如說要湊出10元宗收，如果優(yōu)先使用7元紙幣瞳腌，則張數(shù)是4；（1+1+1+7）
但如果只使用5元紙幣镜雨，則張數(shù)是2嫂侍；（5+5）
在這種情況下，優(yōu)先使用大額紙幣是不正確的貪心選擇荚坞。（但用動態(tài)規(guī)劃仍能得到最優(yōu)解）

2挑宠、服務(wù)器任務(wù)安排問題

服務(wù)器有n個任務(wù)要執(zhí)行，每個任務(wù)有開始時間Si秒和結(jié)束時間Ti秒颓影，同一時間只能執(zhí)行一個任務(wù)各淀。
問如何安排任務(wù)，使得在時間m內(nèi)盡可能多的完成任務(wù)诡挂。

如果是動態(tài)規(guī)劃：
前i秒的完成的任務(wù)數(shù)碎浇，可以由前面1~i-1秒的任務(wù)完成數(shù)推過來。
我們用dp[i]表示前i秒能完成的任務(wù)數(shù)璃俗；
在計算前i秒能完成的任務(wù)數(shù)時奴璃，對于第j個任務(wù)，我們有兩種決策：
1城豁、不執(zhí)行這個任務(wù)苟穆，那么dp[i]沒有變化；
2唱星、執(zhí)行這個任務(wù)雳旅，那么必須騰出來(Sj, Tj)這段時間，那么dp[i] = max(dp[i], dp[ S[j] ] ) + 1间聊；
比如說對于任務(wù)j如果是第5秒開始第10秒結(jié)束攒盈，如果i>=10，那么有dp[i]=max(dp[i], dp[5] + 1)哎榴；（相當(dāng)于把第5秒到第i秒的時間分配給任務(wù)j）

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

小明在學(xué)校兼職叹话，小明一天兼職的時間有10個小時偷遗；
現(xiàn)在有多個兼職崗位，每個崗位有個開始時間和結(jié)束時間驼壶，小明同一時間只能做一個兼職氏豌；
問小明每天最多能做幾份兼職？

我們自然而然會想到一個策略：先把結(jié)束時間早的兼職給做了热凹！
為什么泵喘？
因為先做完這個結(jié)束時間早的泪电，能留出更多的時間做其他兼職。
我們天生具備了這種優(yōu)化決策的能力纪铺。

3相速、分糖果問題

n個小朋友玩完游戲后形庭，老師準(zhǔn)備給他們發(fā)糖果敷扫；
每個人有一個分數(shù)a[i]，如果比左右的人分數(shù)高睦袖，那么糖果也要比左右的多芜繁，并且每個小朋友至少有一顆旺隙。
問老師最少準(zhǔn)備多少糖果。

這是一道LeetCode題目骏令。
這個題目不能直接用動態(tài)規(guī)劃去解蔬捷，比如用dp[i]表示前i個人需要的最少糖果數(shù)。
因為（前i個人的最少糖果數(shù)）這種狀態(tài)表示會收到第i+1個人的影響榔袋，如果a[i]>a[i+1]周拐，那么第i個人應(yīng)該比第i+1個人多。
即是這種狀態(tài)表示不具備無后效性凰兑。

如果是我們分配糖果妥粟，我們應(yīng)該怎么分配？
答案是：從分數(shù)最低的開始聪黎。
按照分數(shù)排序罕容，從最低開始分，每次判斷是否比左右的分數(shù)高稿饰。
假設(shè)每個人分c[i]個糖果，那么對于第i個人有c[i]=max(c[i-1],c[c+1])+1; （c[i]默認為0露泊，如果在計算i的時候,c[i-1]為0喉镰，表示i-1的分數(shù)比i高）
但是，這樣解決的時間復(fù)雜度為O(NLogN)惭笑，主要瓶頸是在排序侣姆。
如果提交，會得到Time Limit Exceeded的提示沉噩。

我們需要對貪心的策略進行優(yōu)化：
我們把左右兩種情況分開看捺宗。
如果只考慮比左邊的人分數(shù)高時，容易得到策略：
從左到右遍歷川蒙，如果a[i]>a[i-1]蚜厉，則有c[i]=c[i-1]+1；否則c[i]=1畜眨。

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

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

4辜伟、小船過河問題

n個人要過河，但是只有一艘船脊另；船每次只能做兩個人游昼，每個人有一個單獨坐船的過河時間a[i]，如果兩個人(x和y)一起坐船尝蠕，那過河時間為a[x]和a[y]的較大值烘豌。
問最短需要多少時間，才能把所有人送過河看彼。

題目給出關(guān)鍵信息：1廊佩、兩個人過河，耗時為較長的時間靖榕；
還有隱藏的信息：2标锄、兩個人過河后，需要有一個人把船開回去茁计；
要保證總時間盡可能小料皇，這里有兩個關(guān)鍵原則：應(yīng)該使得兩個人時間差盡可能小（減少浪費）星压，同時船回去的時間也盡可能屑痢（減少等待）。

先不考慮空船回來的情況娜膘，如果有無限多的船逊脯，那么應(yīng)該怎么分配？
答案：每次從剩下的人選擇耗時最長的人竣贪，再選擇與他耗時最接近的人军洼。

再考慮只有一條船的情況，假設(shè)有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的選擇，我們發(fā)現(xiàn)差別僅在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個人的時候尊流，我們已經(jīng)明顯發(fā)了一個特點：問題是重復(fù)帅戒，且可以由子問題去解決。
根據(jù)5個人的情況，我們可以推出狀態(tài)轉(zhuǎn)移方程dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根據(jù)我們考慮的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]);

由上述的狀態(tài)轉(zhuǎn)移方程和初始化值腻贰，我們可以推出dp[n]的值。

這是一道貪心和動態(tài)規(guī)劃的結(jié)合題目扒秸，動態(tài)規(guī)劃的決策過程中用到了貪心的策略播演。

總結(jié)

貪心的學(xué)習(xí)過程，就是對自己的思考進行優(yōu)化伴奥。
是把握已有信息写烤，進行最優(yōu)化決策。
這里還有一些收集的貪心練習(xí)題拾徙，可以實踐練習(xí)洲炊。
這里還有在線分享，歡迎報名尼啡。