二、湊零錢問題
先看下題目:給你k
種面值的硬幣,面值分別為c1, c2 ... ck
,每種硬幣的數量無限,再給一個總金額amount
,問你最少需要幾枚硬幣湊出這個金額,如果不可能湊出,算法返回 -1 。算法的函數簽名如下:
// coins 中是可選硬幣面值,amount 是目標金額
int coinChange(int[] coins, int amount);
比如說k = 3
,面值分別為 1,2,5,總金額amount = 11
。那么最少需要 3 枚硬幣湊出,即 11 = 5 + 5 + 1。
你認為計算機應該如何解決這個問題?顯然,就是把所有肯能的湊硬幣方法都窮舉出來,然后找找看最少需要多少枚硬幣。
1、暴力遞歸
首先,這個問題是動態規劃問題,因為它具有「最優子結構」。 要符合「最優子結構」,子問題間必須互相獨立 。啥叫相互獨立?你肯定不想看數學證明,我用一個直觀的例子來講解。
比如說,你的原問題是考出最高的總成績,那么你的子問題就是要把語文考到最高,數學考到最高…… 為了每門課考到最高,你要把每門課相應的選擇題分數拿到最高,填空題分數拿到最高…… 當然,最終就是你每門課都是滿分,這就是最高的總成績。
得到了正確的結果:最高的總成績就是總分。因為這個過程符合最優子結構,“每門科目考到最高”這些子問題是互相獨立,互不干擾的。
但是,如果加一個條件:你的語文成績和數學成績會互相制約,此消彼長。這樣的話,顯然你能考到的最高總成績就達不到總分了,按剛才那個思路就會得到錯誤的結果。因為子問題并不獨立,語文數學成績無法同時最優,所以最優子結構被破壞。
回到湊零錢問題,為什么說它符合最優子結構呢?比如你想求amount = 11
時的最少硬幣數(原問題),如果你知道湊出amount = 10
的最少硬幣數(子問題),你只需要把子問題的答案加一(再選一枚面值為 1 的硬幣)就是原問題的答案,因為硬幣的數量是沒有限制的,子問題之間沒有相互制,是互相獨立的。
那么,既然知道了這是個動態規劃問題,就要思考 如何列出正確的狀態轉移方程 。
先確定「狀態」 ,也就是原問題和子問題中變化的變量。由于硬幣數量無限,所以唯一的狀態就是目標金額amount
。
然后確定dp
函數的定義 :函數 dp(n)表示,當前的目標金額是n
,至少需要dp(n)
個硬幣湊出該金額。
然后確定「選擇」并擇優 ,也就是對于每個狀態,可以做出什么選擇改變當前狀態。具體到這個問題,無論當的目標金額是多少,選擇就是從面額列表coins
中選擇一個硬幣,然后目標金額就會減少:
# 偽碼框架
def coinChange(coins: List[int], amount: int):
# 定義:要湊出金額 n,至少要 dp(n) 個硬幣
def dp(n):
# 做選擇,需要硬幣最少的那個結果就是答案
for coin in coins:
res = min(res, 1 + dp(n - coin))
return res
# 我們要求目標金額是 amount
return dp(amount)
最后明確 base case ,顯然目標金額為 0 時,所需硬幣數量為 0;當目標金額小于 0 時,無解,返回 -1:
def coinChange(coins: List[int], amount: int):
def dp(n):
# base case
if n == 0: return 0
if n < 0: return -1
# 求最小值,所以初始化為正無窮
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
# 子問題無解,跳過
if subproblem == -1: continue
res = min(res, 1 + subproblem)
return res if res != float('INF') else -1
return dp(amount)
至此,狀態轉移方程其實已經完成了,以上算法已經是暴力解法了,以上代碼的數學形式就是狀態轉移方程:
至此,這個問題其實就解決了,只不過需要消除一下重疊子問題,比如amount = 11, coins = {1,2,5}
時畫出遞歸樹看看:
時間復雜度分析:子問題總數 x 解決每個子問題的時間 。
子問題總數為遞歸樹節點個數,這個比較難看出來,是 O(n^k),總之是指數級別的。每個子問題中含有一個 for 循環,復雜度為 O(k)。所以總時間復雜度為 O(k * n^k),指數級別。
2、帶備忘錄的遞歸
只需要稍加修改,就可以通過備忘錄消除子問題:
def coinChange(coins: List[int], amount: int):
# 備忘錄
memo = dict()
def dp(n):
# 查備忘錄,避免重復計算
if n in memo: return memo[n]
if n == 0: return 0
if n < 0: return -1
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
if subproblem == -1: continue
res = min(res, 1 + subproblem)
# 記入備忘錄
memo[n] = res if res != float('INF') else -1
return memo[n]
return dp(amount)
不畫圖了,很顯然「備忘錄」大大減小了子問題數目,完全消除了子問題的冗余,所以子問題總數不會超過金額數 n,即子問題數目為 O(n)。處理一個子問題的時間不變,仍是 O(k),所以總的時間復雜度是 O(kn)。
3、dp 數組的迭代解法
當然,我們也可以自底向上使用 dp table 來消除重疊子問題,dp
數組的定義和剛才dp
函數類似,定義也是一樣的:
dp[i] = x
表示,當目標金額為i
時,至少需要x
枚硬幣 。
int coinChange(vector<int>& coins, int amount) {
// 數組大小為 amount + 1,初始值也為 amount + 1
vector<int> dp(amount + 1, amount + 1);
// base case
dp[0] = 0;
for (int i = 0; i < dp.size(); i++) {
// 內層 for 在求所有子問題 + 1 的最小值
for (int coin : coins) {
// 子問題無解,跳過
if (i - coin < 0) continue;
dp[i] = min(dp[i], 1 + dp[i - coin]);
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
PS:為啥dp
數組初始化為amount + 1
呢,因為湊成amount
金額的硬幣數最多只可能等于amount
(全用 1 元面值的硬幣),所以初始化為amount + 1
就相當于初始化為正無窮,便于后續取最小值。
三、最后總結
第一個斐波那契數列的問題,解釋了如何通過「備忘錄」或者「dp table」的方法來優化遞歸樹,并且明確了這兩種方法本質上是一樣的,只是自頂向下和自底向上的不同而已。
第二個湊零錢的問題,展示了如何流程化確定「狀態轉移方程」,只要通過狀態轉移方程寫出暴力遞歸解,剩下的也就是優化遞歸樹,消除重疊子問題而已。
如果你不太了解動態規劃,還能看到這里,真得給你鼓掌,相信你已經掌握了這個算法的設計技巧。
計算機解決問題其實沒有任何奇技淫巧,它唯一的解決辦法就是窮舉 ,窮舉所有可能性。算法設計無非就是先思考“如何窮舉”,然后再追求“如何聰明地窮舉”。
列出動態轉移方程,就是在解決“如何窮舉”的問題。之所以說它難,一是因為很多窮舉需要遞歸實現,二是因為有的問題本身的解空間復雜,不那么容易窮舉完整。
備忘錄、DP table 就是在追求“如何聰明地窮舉”。用空間換時間的思路,是降低時間復雜度的不二法門,除此之外,試問,還能玩出啥花活?
-
計算機
+關注
關注
19文章
7488瀏覽量
87854 -
函數
+關注
關注
3文章
4327瀏覽量
62573 -
動態規劃
+關注
關注
0文章
17瀏覽量
8914
發布評論請先 登錄
相關推薦
評論