問題描述
設有n種不同面值的硬币，各硬币的面值存于數組T[1:n]中。現要用這些面值的硬币來找錢，可以實用的各種面值的硬币個數不限。當隻用硬币面值T[1],T[2],…,T[i]時，可找出錢數j的最少硬币個數記為C(i,j)。若隻用這些硬币面值，找不出錢數j時，記C(i,j)=∞。
« 程式設計任務
設計一個動态規劃算法，對1≤j≤L，計算出所有的C( n,j )。算法中隻允許實用一個長度為L的數組。用L和n作為變量來表示算法的計算時間複雜性
« 資料輸入
從螢幕輸入資料。輸入第1行中有1個正整數n（n<=13），表示有n種硬币可選。接下來的一行是每種硬币的面值。由使用者輸入待找錢數j。
« 結果輸出
程式運作結束時，将計算出的所需最少硬币個數輸出到螢幕。
| 輸入示例 | 輸出檔案示例 |
| 3 1 2 5 9 | 3 |
建立二維動态規劃表
m為該次需要找的錢數，
i為所用錢的種類數，
邊界條件：
1）當找不開時，C[i][m]=∞
2）當m=0時，C[i][m]=0
遞歸關系：
但是要注意找不開的情況，
隻有m>=t[i-1]時，才會走：
m<t[i-1]直接用：
程式設計檢驗的時候可以使用
3
2 3 5
6
這個例子
def give_coins(t,amount):
maxc=(float('inf'))
lent=len(t)
C=[[maxc for i in range(amount+1)] for k in range(lent+1)]
for i in range(lent+1):
for m in range(amount+1):
if i==0: #初始化第一行
C[i][m]=maxc
elif m==0: #初始化第一列
C[i][m]=0
else:
if m-t[i-1]>=0:
C[i][m]=min(C[i][m-t[i-1]]+1,C[i-1][m])
else:
C[i][m]=C[i-1][m]
return C
#回溯（未成功）
# def back(t,c):
# select=[]
# lent=len(t)
# import numpy as np
# minc=(np.min(C,axis=0))[-1] #數組C最後一列的最小值
# minarg=(np.argmin(C,axis=0))[-1] #數組C最後一列最小值的下标
# while minc>0:
# minc-=t[lent-1]
# minarg-=t[lent-1]
if __name__=="__main__":
n=(int)(input())
#小菜鳥剛學會把n個數輸入到清單中
lista=[int(i) for i in input().split()]
# print(lista)
amount=(int)(input())
result=give_coins(lista,amount)
#動态規劃表
# for list in result:
# print(list)
import numpy as np
minc=(np.min(result,axis=0))[-1] #數組C最後一列的最小值
print(int(minc))