此節需要回顧前面的動態規劃自底向上的計算方法和禮物問題，自底向上的計算辦法是為了求出需要的硬幣個數，後者是為了求出具體的硬幣組合

零錢兌換

給定不同面值的硬幣coins（理解成一個數組）和一個總金額s,編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額返回-1,(每種硬幣的數量是無限的, s以及coins中的元素都是正整數
假設我們要湊總金額為11，我們有1，2，5，20這四個面值的硬幣，現在要求出最少需要的硬幣個數和組合，我們不妨先畫個圖自己走一遍，可以發現可以發現1,5，5就是我們要求的，而10這一層向上就需要一個硬幣即
F（11）=min(F（10）)+1 意思是面值為11的情況等於 面值為10的最少硬幣組合+一個1塊的硬幣.
以此類推
F（10）=min(F（5）)+1 意思是面值為10的情況等於 面值為5的最少硬幣組合+一個5塊的硬幣.
而這種至上而下的算法就是我們之前提到的迭代，十分耗費時間，所以我們采取至下而上的算法，從f（1）開始到f（11）

最後f（11）的個數就是3，就是最小硬幣個數，

得出硬幣組合

在我們這個表中, FF(11)-3,我們將3減去1得到2,然後在表格中找到: f(11-1),f(11-2),f(11-5)中哪一個是2,顯然,f(10)=2.f(9)=3,f(6)=2,這裡出現了兩個2,說明可能出現了兩個不同的方案,我們只需要選擇任意一個就行,比如我們選擇f(6),從x=6變成x=11需要一枚面值為5(11-6)的硬幣,因此我們將5添加到IND中。(注意:在這一步的時候我們也可以直接判斷f(10),f(9)和f(6)哪個最小,因為我們始終選擇的是f(x-c)較小的那種情況

%% 怎麼得到具體的硬幣組合
function [f, IND] = coin_change2(coins, S)
FF = +inf * ones(1,S+2);
FF(S+2) = 0; % 最後一個元素改為0
for x = 1:S
tmp = x - coins;
tmp(tmp<0) = S+1;
tmp(tmp==0) = S+2;
FF(x) = min(FF(tmp))+1;
end
% 利用FF來計算IND
IND = []; % IND表示我們選擇的硬幣組合，初始化為空向量
if FF(S) < +inf % 存在能湊成S的組合
f = FF(S);
ind = S; % ind先指向最後一個位置S
while FF(ind) > 1 % 如果FF(ind) = 1時就不用尋找了
indd = ind; % 保存前一個位置
tmp = ind - coins;
tmp(tmp<0) = S+1; % FF下標為S+1的元素為+inf
tmp(tmp==0) = S+2; % FF最後一個元素為0
ind = tmp(find(FF(tmp) == (FF(ind) -1),1)); % 找到新的位置
IND = [IND,indd-ind]; % 兩個位置之差就是我們要添加的硬幣
end
IND = [IND,ind]; % FF(ind) = 1時，把ind也放入到IND中
else % 如果沒有任何一種硬幣組合能組成總金額S就返回-1
f = -1;
end
end

import numpy as np
class solution():
########定義你的硬幣，和需要湊出來的總數S#######
coins=[1,2,5,20]
S=11
#####################
Coins=np.array(coins)
FF = float("inf")*np.ones(S+2)
FF[S+1] = 0
#獲取
def get_num(self):
for x in range(1,self.S+1):
tmp = x-self.Coins
tmp[tmp<0]= self.S+1
tmp[tmp==0]= self.S+2
self.FF[x-1]=min(self.FF[tmp-1])+1
if self.FF[self.S-1]< float("inf"):
f = self.FF[self.S-1]
return f
else:
return -1
def get_combination(self,f):
if f!=-1:
ind = self.S
IND=[]
while self.FF[ind-1] >1:
indd = ind
tmp = ind - self.Coins
tmp[tmp<0]= self.S+1
tmp[tmp==0]= self.S+2
ind =
IND.append(indd-ind)
IND.append(ind) #==1時的也加進去
return IND
else:
return -1
leedcode322=solution()
f=leedcode322.get_num()
c=leedcode322.get_combination()
print(f)
print(c)