貪心，貪心和動歸
貪心算法(Greedy Algorithm)就是把問題分解成很多個子問題，從從子問題中找到最優(yōu)解，組合成總的最優(yōu)解。
這個想法跟動態(tài)規(guī)劃很像冯事，不同的是動態(tài)規(guī)劃的每個子問題都會影響下一個子問題，最后會完全match到結(jié)果的要求血公，而貪心法得到的很可能只是接近最優(yōu)昵仅。
要說明他們的區(qū)別，典型的例子就是背包問題累魔，小偷去偷東西摔笤，有多個不同價值w、不同體積v的物品可以拿垦写，但只有一個容量為n的包吕世；如果是0-1背包問題，用貪心的思想的話梯投，就會先裝w/v單位價值最大的物品命辖，裝滿了就拿第二大的，直到裝不下晚伙，這當(dāng)然沒有考慮背包是不是會有空余的體積沒有裝滿造成的浪費(fèi)吮龄；而動態(tài)規(guī)劃就會直接考慮到包的容量是不是正好裝滿，它的每一個子步驟都會影響下一個子步驟咆疗。
安排教室
一個典型的貪心法的例子是活動安排問題漓帚，也是算法導(dǎo)論上的一個例子：
有n個活動的集合E = {1,2,…,n}，其中每個活動都要求使用同一資源午磁，如演講會場等尝抖，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si < fi 迅皇。如果選擇了活動i昧辽，則它在半開時間區(qū)間[si, fi)內(nèi)占用資源。若區(qū)間[si, fi)與區(qū)間[sj, fj)不相交登颓，則稱活動i與活動j是相容的搅荞。也就是說，當(dāng)si >= fj或sj >= fi時框咙，活動i與活動j相容咕痛。安排盡可能多的活動。
可以理解成這些活動都要在一間教室舉行喇嘱，怎么才能安排盡可能多的活動呢茉贡。
用貪心的思想，我們只希望當(dāng)前活動時間結(jié)束地越早越好者铜，這樣就能給后面的活動留出更多的時間腔丧。不需要考慮后面活動的長短和沖突放椰。正好，給出的表格是按照時間結(jié)束時間順序排列的愉粤。如果不是砾医，就用快速排序O(nlogn)時間排列一下。
下面的圖是加入活動的迭代順序科汗，復(fù)雜度O(n)藻烤，非常直觀。
哈夫曼編碼/哈夫曼樹
這個是考研的時候必須會畫的一張圖了头滔，理解起來很簡單怖亭。
首先哈夫曼編碼是壓縮文件常用的算法。比如abcde5個字母組成的文件坤检，出現(xiàn)的頻次不同兴猩，我們怎么做才能壓縮文件呢？當(dāng)然是要先編碼（壓縮）早歇，再解碼（解壓縮）倾芝。把頻次高的字母用短的符號表示，頻次低的字母用長的符號表示箭跳。對了晨另，這要求這些用來表示的符號是「前綴碼」，這樣才能解碼谱姓。
下面這張圖是構(gòu)造哈夫曼樹的過程借尿，構(gòu)造完了之后，哈夫曼編碼自然而然就地出來了屉来。對照構(gòu)造的過程來看吧路翻。完成之后的左子樹對應(yīng)0，右子樹對應(yīng)1茄靠。比如節(jié)點3就是101茂契。這個是標(biāo)準(zhǔn)的前綴碼。
構(gòu)造哈夫曼樹的算法：
- 對給定的n個權(quán)值{W1,W2,W3,...,Wi,...,Wn}構(gòu)成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,..., Tn}慨绳，其中每棵二叉樹Ti中只有一個權(quán)值為Wi的根結(jié)點掉冶，它的左右子樹均為空。
- 在F中選取兩棵根結(jié)點權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹脐雪，新二叉樹的根結(jié)點的權(quán)值為其左右子樹的根結(jié)點的權(quán)值之和厌小。
- 從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中喂江。
- 重復(fù)2）和3），直到集合F中只有一棵二叉樹為止旁振。
哈夫曼編碼的過程體現(xiàn)了貪心法的兩個要點：
(1)貪心選擇性質(zhì)
(2)最優(yōu)子結(jié)構(gòu)性質(zhì)
JumpGame
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
這個問題有點像動態(tài)規(guī)劃也有點像貪心获询。
說它像貪心是因為它只要判斷當(dāng)前的index上對應(yīng)的num是不是能reach到last index涨岁，說它像動歸是因為對于[0,2,3]這種test case，只考慮當(dāng)前是不行的吉嚣，因為0不能reach而2能reach梢薪，你不能直接遍歷每個index能reach就返回true否則返回false，還需要維護(hù)一個能reach到的最遠(yuǎn)距離尝哆。
這題目給出這樣的解法：
public boolean canJump(int[] nums) {
int maxCover = 0;
for (int i = 0; i <= nums.length - 1 && i <= maxCover; i++) {
maxCover = Math.max(maxCover,nums[i]+i);//遞推
if (maxCover>=nums.length-1) return true;
}
return false;
}
或許可以稱為一個有遞推式的貪心算法吧秉撇。
注意，本文只是講了皮毛秋泄。
Reference:
[1]http://www.cnblogs.com/chinazhangjie/archive/2010/11/23/1885330.html
[2]http://www.cnblogs.com/phoenixzq/archive/2011/10/19/2217346.html
