# 找零問題
def coinChange(coins, amount):
"""
:type coins: List[int]
:type amount: int
:return: num of used coins
"""
dp = [amount + 1 for _ in range(amount + 1)]
used = [0 for _ in range(amount + 1)]
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
if dp[i] > dp[i - coin] + 1:
dp[i] = dp[i - coin] + 1
used[i] = coin
return used, dp[amount] if dp[amount] < amount + 1 else -1
def used_detail(coins, used, amount):
dicts = {i: 0 for i in coins}
while amount > 0:
dicts[used[amount]] += 1
amount -= used[amount]
return dicts
coins = [1,2,5,10]
amount = 63
used, num = coinChange(coins, amount)
d = used_detail(coins, used, 63)
print('number of coins: ', num)
print(d)
找零問題
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來咏瑟，“玉大人拂到，你說我怎么就攤上這事÷肱ⅲ” “怎么了兄旬？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長余寥。 經(jīng)常有香客問我领铐，道長，這世上最難降的妖魔是什么宋舷？ 我笑而不...
- 正文 為了忘掉前任绪撵，我火速辦了婚禮，結(jié)果婚禮上祝蝠，老公的妹妹穿的比我還像新娘音诈。我一直安慰自己，他們只是感情好绎狭，可當我...
- 文/花漫 我一把揭開白布细溅。 她就那樣靜靜地躺著，像睡著了一般坟岔。 火紅的嫁衣襯著肌膚如雪谒兄。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼啊研，長吁一口氣：“原來是場噩夢啊……” “哼御滩！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起党远，我...
- 正文 年R本政府宣布，位于F島的核電站柿赊，受9級特大地震影響俩功，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜碰声，卻給世界環(huán)境...
- 文/蒙蒙 一诡蜓、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧胰挑，春花似錦蔓罚、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至贡这，卻和暖如春茬末，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背。 一陣腳步聲響...
