接上文：【README2】動態(tài)規(guī)劃之斐波那契數列說明重疊子問題如何解決

文章目錄

• 找零錢問題說明最優(yōu)子結構
• • （1）何為最優(yōu)子結構
  • （2）狀態(tài)轉移方程 暴力解法
  • （3）備忘錄解決重疊子問題
  • （4）迭代解法

找零錢問題說明最優(yōu)子結構

lLeetCode 509：零錢兌換

（1）何為最優(yōu)子結構

這里面的子結構其實指的就是子問題，但是要成為最優(yōu)子結構必須滿足子問題之間相互獨立

舉個例子：如果你的終極問題是考的最高的成績，那么你的子問題就是如何把數學考的最高分，如何把語文考到最高分…這里很明顯可以發(fā)現，數學和語文以及其他科目的成績不會相互制約，所以這個過程符合最優(yōu)子結構。一旦子問題之間相互干擾，比如數學考的越高，語文考的越低，那么永遠也無法得到最高分，這就不是最優(yōu)子結構

回到湊零錢的問題來，它就很好的滿足了最優(yōu)子結構。以下面這個例子為例

你想要解決“如何以最少的硬幣湊夠11元”的問題，那么那就需要先解決“如何以最少的硬幣湊夠10元”的子問題，因為一旦滿足剛才的子問題，只需要加上一塊硬幣（面值為1）就能解決終極問題了。

（2）狀態(tài)轉移方程 暴力解法

前文就說過，暴力解法本質體現的就是狀態(tài)轉移方程，一旦能夠列出狀態(tài)轉移方程，剩余的只是一些比較容易的優(yōu)化工作

所以這里我們按照之前列狀態(tài)轉移方程的思路，進行探求

base case（最簡單的情況）是什么：很顯然使目標金額如果為0，就讓程序返回0，此時不需要任何硬幣就可以湊出目標金額了

這個問題有什么狀態(tài)？也即是原問題和子問題的變量：也很簡單，金額數是在不斷變化的，不斷向base case靠近。

每個狀態(tài)可以做怎樣得到選擇使得狀態(tài)變化：這也很清晰，每次進入遞歸時可以選擇一個面值的硬幣，相當于減少了目標金額數

如何定義dp數組或遞歸函數來表達狀態(tài)和選擇：見下

我們說過暴力解法實則就是自頂向下的過程，所以這里定義的dp函數的參數一般就是狀態(tài)轉移中的變量，函數的返回值則是題目讓我們求的值
就這道題而言，能很明確金額數可以作為函數形參，返回值就是要求的硬幣的數量

根據以上思路，寫出算法的偽代碼

def coinChange(coins:List[int],amout:int) {#定義：要湊出金額n，至少需要dp[n]枚硬幣def dp[n]:#做選擇，選擇需要硬幣最少的那個結果for coin in coinsres=min(res,1+dp[n-coin])return res#題目最終要求的結果是amountreturn dp[amount]; }

如下，根據偽代碼我們可以寫出暴力解法的代碼

class Solution { public:int dp(vector<int>& coins,int n){if (n==0) return 0;if (n<0) return -1;//base caseint res=INT_MAX;//INT_MAX代表永遠都取不到，for(size_t i=0;i<coins.size();i++){int subproblem=dp(coins,n-coins[i]);//狀態(tài)變化，選擇了一塊硬幣，金額就變少了if(subproblem==-1)//如果等于-1表明行不通，繼續(xù)下一個continue;res=min(res,1+subproblem);//始終保持最小}if (res!=INT_MAX)//永遠都取不到就會返回-1return res;elsereturn -1;}int coinChange(vector<int>& coins, int amount) {return dp(coins,amount);} };

暴力解法就代表了狀態(tài)轉移方程，所以它的狀態(tài)轉移方程為

當然這道題是無法通過的，因為暴力解法時間復雜度太大

畫出遞歸樹，就可以看見很多重疊子問題沒有解決

（3）備忘錄解決重疊子問題

所以為了降低時間復雜度，我們設置一個備忘錄，如果有值就直接拿取

class Solution { public:int dp(vector<int>& coins,int n,unordered_map<int,int>& memory){//每次進入dp后首先查備忘錄if(memory.find(n)!=memory.end())return memory[n];if (n==0) return 0;if (n<0) return -1;//base case int res=INT_MAX;for(size_t i=0;i<coins.size();i++){int subproblem=dp(coins,n-coins[i],memory);if(subproblem==-1)continue;res=min(res,1+subproblem);memory[n]=res;//加入備忘錄}if (res!=INT_MAX){return memory[n];}elsereturn -1;}int coinChange(vector<int>& coins, int amount) {unordered_map<int,int> memory;return dp(coins,amount,memory);} };

（4）迭代解法

如果采用迭代解法解決，則和前面的有所區(qū)別，前面的dp函數中，參數列表是狀態(tài)，返回值是目標值。如果采用迭代寫法，那么索引就是狀態(tài)，索引對應的數組值就是返回結果

class Solution { public:int coinChange(vector<int>& coins, int amount) {//amount金額的硬幣最多需要amount塊硬幣（全為1，初始化amount+1相當于是正無窮，方面后續(xù)取最小值）vector<int> dp(amount+1,amount+1);dp[0]=0;//base casefor(int i=0 ;i < dp.size();i++)//最外層的for循環(huán)遍歷的是每個狀態(tài){for(auto coin : coins)//該for循環(huán)用于求所有選擇的最小值{if(i-coin<0)//子問題無解continue;dp[i]=min(dp[i],1+dp[i-coin]);//狀態(tài)轉移，想象11和10的關系}}return (dp[amount]==amount+1) ? -1 : dp[amount];} };

總結

以上是生活随笔為你收集整理的【README3】动态规划之“找零钱”说明最优子结构怎么解决的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。