當(dāng)貪心失效了上一課我們學(xué)習(xí)算法提出硬幣找零的問題發(fā)現(xiàn)

貪心算法失效的很大一個(gè)原因在于它明顯的局限性：它幾乎只考慮局部最優(yōu)解。所謂局部最優(yōu)，就是只考慮當(dāng)前的最大利益，既不向前多看一步，也不向后多看一步，導(dǎo)致每次都只用當(dāng)前階段的最優(yōu)解。似。同時(shí)，也是所有討論最優(yōu)化問題的基礎(chǔ)。既然無法通過貪心算法達(dá)到整體最優(yōu)，我們就得換一個(gè)思路了：我們得從整體最優(yōu)的層面上解決這個(gè)難纏的算法問題。那么從何說起呢？我認(rèn)為你應(yīng)該先理解最優(yōu)化問題的本質(zhì)，然后再把這個(gè)思考擴(kuò)展到遞歸問題上。話不多說，我們這就開始吧！如果只是從概念上來看最優(yōu)化的是玄而又玄，所以在上一課中我用了硬幣找零的例y53最少硬幣數(shù)量就是5元硬幣和3元硬幣的總數(shù)，假定5元硬幣數(shù)量為x0，3元硬幣數(shù)量為x1，那么用函數(shù)表示就是：f(x0,x1)=x0+53的面值綜合為y。為此我們需要給出一個(gè)約束：5x0+3x1=x0和，使得目標(biāo)函數(shù)f(x0,x1)的取值最小。如果用數(shù)學(xué)的描述方法來說的話，就是下面這argmin(x0,x1)∈S(x0+這個(gè)就是我們常見的argmin表示方式。它的意思是：當(dāng)(x0,x1)屬于S這個(gè)集合的時(shí)候，希望知道x0+x1的最小值是多少。其中S集合的條件就是上面的約束。回到硬幣找零這個(gè)問題上。由于(x0,x1)(x0,x1) 件的組合(x0,x1)中找出一個(gè)組合，使得x0+x1的值最小。所以，你會(huì)發(fā)現(xiàn)在這種離散型的最優(yōu)化問題中，本質(zhì)就是從所有滿足條件的組合（能夠湊出y元）中選擇出使得我們的目標(biāo)函數(shù)（所有硬幣數(shù)量之和）最小的那個(gè)組合。而這個(gè)所謂滿足條件的組合不就是argmin中的那個(gè)集合S嗎？因此，這種離散型的最優(yōu)化問題就是去所有滿足條件的組合里找出最優(yōu)解的組合。我曾多次提到的局部最優(yōu)就是在一定條件下的最優(yōu)解，而整體最優(yōu)就是我們真正希望得到的最優(yōu)解。255,0)和(5)，也就是5個(gè)52個(gè)55個(gè)3組合肯定就是(5,0F(n01 F(n)=?

F(n?1)+F(n?2),n>代代12345示例解釋：F(2)=F(1)+F(0)=1+0=1代碼代碼12345示例解釋：F(3)=F(2)+F(1)=1+1=很多人在解算法面試問題的時(shí)候有一種傾向性，那就是使用迭代而非遞歸來求解問題。我先不說這樣的傾向性正確與否，那么我們就按照這個(gè)偏好來解一下（即那契數(shù)列的循環(huán)解法）。Java代代123456789intfibonacci(intn)int[]resolution={0,1};//if(n<2){returnresolution[n];inti=intfib1=0,fib2=1,fib=0;while(i<n){fib=fib1+fib2;fib1=fib2;fib2=fib;}returnfib;//}C代1Fibonacci(intn)2std::vector<int>resolution={0,1};//34if(n<2){returnresolution[n];5inti=6intfib1=0,fib2=1,fib=7while(i<n)8fib=fib1+9fib1=fib2=}returnfib;//15嗯，這樣的解法固然沒錯(cuò)，但是它幾乎脫離了題設(shè)的數(shù)學(xué)表達(dá)形式。在這道題目中，出題者“刻意”地寫出了求解那契數(shù)列的函數(shù)表達(dá)式，這其中有沒有什么別的含義或原因呢？當(dāng)然有了，這個(gè)函數(shù)表達(dá)式很好地反應(yīng)出了計(jì)算機(jī)科學(xué)中常見的算法形式：遞歸。下面，代代123456intFibonacci(intn)if(0==n||1==n){returnn;if(n>1){returnFibonacci(n-1)+Fibonacci(n-2);return0;//如果輸入n}Java1voidgetMinCountsHelper(inttotal,int[]values,ArrayList<Integer>2345678921

if(0==total){//如果余額為0}intvalueLength=for(inti=0;i<valueLength;iintcurrentValue=if(currentValue>total){//}//否則在當(dāng)前面值數(shù)量組合上的對(duì)應(yīng)位置加ArrayList<Integer>newCounts=newArrayList<Integer>(currentCounts);newCounts.set(i,newCounts.get(i)+1);intrest=total-getMinCountsHelper(rest,values,newCounts,combinations);//}intgetMinimumHelper(ArrayList<ArrayList<Integer>>combinations)//如果沒有可用組合，返回-if(0==combinations.size()){return-1;intminCount=for(ArrayList<Integer>counts:combinations)inttotal=0;//for(intcount:counts){total+=count; // if(total<minCount){minCount=total; return}intgetMinCountOfCoins()int[]values={5,3};//inttotal=11;ArrayList<Integer>initialCounts=newgetMinCountsHelper(total,binationsArrayList<>();binations);//returnbinations);//}1voidGetMinCountsHelper(inttotal,conststd::vector<int>&values,2345678921

if(!total){//如果余額為0}intvalueLength=for(inti=0;i<valueLength;iintcurrentValue=if(currentValue>total){//}//否則在當(dāng)前面值數(shù)量組合上的對(duì)應(yīng)位置加1std::vector<int>newCounts=currentCounts;newCounts[i]intrest=total-GetMinCountsHelper(rest,values,newCounts,combinations);//}intGetMinimumHelper(conststd::vector<std::vector<int>>&combinations)//如果沒有可用組合，返回-if(!combinations.size()){return-1;intminCount=for(conststd::vector<int>&counts:combinations)inttotal=0;//for(intcount:counts){total+=count; //if(total<minCount){minCount=total;}return}intGetMinCountOfCoins()std::vector<intvalues={5,3inttotal=11;std::vector<intinitialCounts(values.size(0初始值binations GetMinCountsHelper(total,values,binations);//returnbinations);//}從組合中選出總和最小的組合。如果找不到滿足條件的組合那么就返回-1。Java代代123456789intgetMinCountsHelper(inttotal,int[]values)//如果余額為0if(0==total){return0;intvalueLength=values.length;intminCount=Integer.MAX_VALUE;for(inti=0;i<valueLength;i//intcurrentValue=//if(currentValue>total){continue;intrest=total-currentValue;intrestCount=getMinCountsHelper(rest,//如果返回-1if(restCount==-1){continue;inttotalCount=1+restCount;if(totalCount<minCount){minCount=totalCount;}//如果沒有可用組合，返回-if(minCount==Integer.MAX_VALUE){return-1;returnminCount;}intgetMinCountOfCoinsAdvance()intvalues={3,5//inttotal=11;returngetMinCountsHelper(total,values);//}CintvalueLength=intminCount=for(inti=0;i<valueLength;i++){//intcurrentValue=9//if(currentValue>total){continue;intrest=total-currentValue;//intrestCount=GetMinCountsHelper(rest, //如果返回-1if(restCount-1){continue;inttotalCount1+restCount;//if(totalCountminCount){minCount=totalCount;}std::vector<intvalues={5,3inttotal=11;returnGetMinCountsHelper(total,values);//}在這段代碼中，每一次遞歸返回的值，都是后續(xù)組合之和的最小值。它不再所有的組這樣可以極大節(jié)省空間，這是處理遞歸問題的通用方法。一般來說，你都應(yīng)該用這種在計(jì)算機(jī)中，實(shí)現(xiàn)遞歸必須建立在堆棧的基礎(chǔ)上，這是因?yàn)槊看芜f歸調(diào)用的時(shí)候我們都需要把當(dāng)前函數(shù)調(diào)用中的局部變量保存在某個(gè)特定的地方，等到函數(shù)返回的時(shí)候再把這些局部變量取出來。數(shù)量。而無需用其它方法來當(dāng)前或之前的數(shù)據(jù)。得益于遞歸，我們通過堆棧實(shí)現(xiàn)了狀態(tài)，這樣的代碼看起來簡單、清晰明了。在本節(jié)課稍后的內(nèi)容中，在我講到遞歸樹的求解組合空間時(shí)，你會(huì)更清晰地認(rèn)識(shí)到堆棧和狀態(tài)存儲(chǔ)帶來的價(jià)值！上一課中，我們已經(jīng)提到過回溯的思想。在硬幣找零這個(gè)問題里，具體說就是如果遇到已經(jīng)無法求解的組合，那么我們就往回退一步，修改上一個(gè)面值的硬幣數(shù)量，然后再嘗試新的組合。（斜線）左邊表示當(dāng)前節(jié)點(diǎn)使用的硬幣如果在每個(gè)節(jié)點(diǎn)上加上當(dāng)前這個(gè)節(jié)點(diǎn)求得的組合結(jié)果，就可以用遞歸樹表示求解的組合空間：從上圖中我們可以發(fā)現(xiàn)，每個(gè)節(jié)點(diǎn)都了一個(gè)當(dāng)前求解過程中的組合，和后續(xù)節(jié)點(diǎn)的組而真正的求解組合，就是把所有余額為0代碼可讀性低且調(diào)試。我在這里給你具體分析一下。遞歸的最后一個(gè)特點(diǎn)就是窮舉（都叫，你說是不是）。如果我們只使用樸素的遞歸思路解題，就需要通過遞歸來窮舉出所有的組合，而且我們窮舉的不只是組合，還是所有可能得到目標(biāo)組合的組成路徑！2,525因此，遞歸只是讓問題可以求解，但是如果數(shù)據(jù)規(guī)模過大的時(shí)候遞歸會(huì)極大的性bug，當(dāng)你想嘗試去調(diào)試的時(shí)候，就會(huì)發(fā)現(xiàn)這樣的代碼幾乎沒有調(diào)試你可以從前面的圖中看到，這棵樹中有很多分支是完全相同的：起碼從理論上講最終只有兩個(gè)組合。但是這棵樹到達(dá)同一種組合的路徑卻非常多，所以優(yōu)化遞歸的思路其實(shí)就是如何減少搜索的分支數(shù)量。如果條件再減少一個(gè)，再遞歸搜索。最后的代碼就跟我在上一課中寫給你的回溯請(qǐng)你注意觀察一下：在解空間的圖中，只要是余額相同的情況下，后面的搜索路徑是完全12這是一個(gè)重要線索，在這個(gè)硬幣求解問題中，當(dāng)余額相同的時(shí)候，最優(yōu)解是確定的。那么你想想看，如果能夠避免相同余額下的重復(fù)搜索過程，那么算法執(zhí)行速度是不是可以加快了？你可以把求解12252512自然地，枚舉是獲得最優(yōu)解的理想方法。而遞歸可以幫助我們獲得所有可能答案的組合。遞歸形式的求解幾乎就是簡單地把題設(shè)中的函數(shù)表達(dá)式照搬過來，它相較于迭代來說更直觀，且易于理解。但遞歸有著十分明顯的缺陷，存在性能低下、可讀性低和調(diào)試等問題。為此，我但在稍復(fù)雜的面試問題面前，我們還需要借助于更高級(jí)的：備忘錄和動(dòng)態(tài)規(guī)劃。而重疊子問題是理解這些高級(jí)的基礎(chǔ)，下節(jié)課我會(huì)具體來講。 歸科技所有 不得售賣。頁面已增加防盜追蹤，將依法其下一 03|備忘錄：如何避免遞歸中的重復(fù)計(jì)算言言聲{vector<string>generateParenthesis(intn)1 351//List<Integer>initialCounts=new//Collections.fill(initialCounts,List<Integer>initialCounts=Arrays.stream(new作者回復(fù):感謝你，這里使用了ArrayList<Integer>initialCounts=newArrayList<>(Collections.nCopies(values.l