快捷導(dǎo)航

Python零錢兌換的實(shí)現(xiàn)代碼

更新時(shí)間：2022年05月09日 11:20:21 作者：亖夕

假如有這樣一個(gè)問題給你一個(gè)整數(shù)數(shù)組?coins?，表示不同面額的硬幣以及一個(gè)整數(shù)?amount?，表示總金額，計(jì)算并返回可以湊成總金額所需的最少的硬幣個(gè)數(shù)，接下來通過示例代碼給大家介紹Python零錢兌換問題，感興趣的朋友一起看看吧

題目：

給你一個(gè)整數(shù)數(shù)組 coins ，表示不同面額的硬幣；以及一個(gè)整數(shù) amount ，表示總金額。

計(jì)算并返回可以湊成總金額所需的最少的硬幣個(gè)數(shù) 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。你可以認(rèn)為每種硬幣的數(shù)量是無限的。

示例 1：

輸入：coins = [1, 2, 5], amount = 11

輸出：3

解釋說明：11 = 5 + 5 + 1

示例 2：

輸入：coins = [2], amount = 3

輸出：-1

解釋說明：硬幣無法湊成金額-1

示例 3：

輸入：coins = [1], amount = 0

輸出：0

題目分析：

題目要求用最少的硬幣個(gè)數(shù)湊出總金額amount。我們第一感覺可能是使用暴力或者遞歸解題，對這道題使用暴力解題，計(jì)算出所有可能的結(jié)果后取硬幣數(shù)最小值，時(shí)間復(fù)雜度妥妥O(n^3），算是很慢的解題方式了，下面我們介紹遞歸解法和玄學(xué)位運(yùn)算解法（使用到位運(yùn)算解法的解題效率一半很高，但是很難想到，所以我愿稱之為“玄學(xué)”）

解題思路：

解法一：遞歸

使用動態(tài)規(guī)劃五部曲

1.分析確定dp數(shù)組以及其下標(biāo)的含義或狀態(tài)分析

我們規(guī)定dp[i]表示湊足總額為 i 所需錢幣的最少個(gè)數(shù)。

2.確定遞推公式

我們考慮dp[i]的來源，因?yàn)閐p[i]的來源為dp[i - coins[i]] + 1，（coins[i]表示coins中的第i枚硬幣），這也是dp[i]的唯一來源。

那為什么要+1呢？

這里我們明確dp[i - coins[i]]是湊夠金額 i - coin[i]的最少硬幣個(gè)數(shù)。那么當(dāng)金額i - coin[i]變到 i 時(shí)，意味著我們在coins中拿了一枚硬幣coins[i]，那么從dp[i - coin[i]] 到 dp[i]需要加上所取得那枚硬幣，即+1.

分析到dp[i]狀態(tài)及前面得狀態(tài)，dp[i]即為最優(yōu)解。

---------------------------------------

如

coins = [1, 2, 3] amount = 5

那么在 1+1+1+1+1 = 5, 1+2+1+1 = 5, 2+2+1 = 5....等情況中

dp[5]最優(yōu)解必為2+2+1 = 5

即dp[5] = dp[5 - coins[0]] + 1

而dp[5 - coins[0]] = dp[4] = dp[4 - coins[1]] + 1

以此類推

------------------------------------------

我們要取最優(yōu)解（硬幣數(shù)最少）也就是取dp[i - coins[i]] + 1最小值

即遞推公式為：dp[i] = min(dp[i - coins[i]] + 1， dp[i])

(括號中得dp[i]為上一狀態(tài)的dp[i])

3.如何初始化dp數(shù)組

我們分析公式的基礎(chǔ)，可得公式基礎(chǔ)為dp[0]即湊足總額為 0 所需錢幣的最少個(gè)數(shù)。接著考慮到其他dp列表其他下標(biāo)的初始化，由于遞推公式使用了min（），那么為了不讓初始化影響遞推結(jié)果，我們需要將dp[i]（i != 0)初始化為一個(gè)很大的數(shù)，如正無窮‘inf’。

4.確定遍歷的順序

題目要求的是找到最小硬幣個(gè)數(shù)，所以遍歷coins或者先遍歷尋找amount列表無關(guān)緊要。

5.舉例驗(yàn)證推導(dǎo)的dp數(shù)組（公式）是否正確

可以帶入一個(gè)簡單以的例子，比如例1.

代碼實(shí)現(xiàn)

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

代碼注釋

def coinChange(coins, amount):
    # 初始化dp列表
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 初始化遞推公式基礎(chǔ)
    for coin in coins:   # 遍歷硬幣
        # 遍歷尋找構(gòu)成amount最優(yōu)解
        for i in range(coin, amount + 1):  
            dp[i] = min(dp[i], dp[i - coin] + 1)
    # 如果最終沒有找到湊成amount金額的硬幣，返回-1
    return dp[amount] if dp[amount] != float('inf') else -1

時(shí)間復(fù)雜度O(nm),n為amoun面額，m為硬幣種數(shù)。空間復(fù)雜度為O(m),即為dp列表所用空間。

解法二：

接下來就是玄學(xué)位運(yùn)算了。先看代碼

代碼實(shí)現(xiàn)

def coinChange(coins, amount):
    if not amount:
        return 0
    dp = 1 << amount
    res = 0
    while dp:
        tmp = 0
        res += 1
        for i in coins:
            tmp |= dp >> i
        if tmp & 1:
            return res
        dp = tmp
    return -1

代碼注釋

def coinChange(coins, amount):
    if not amount:
        return 0
    # 按位左移運(yùn)算構(gòu)造類似dp數(shù)組的記錄二進(jìn)制
    dp = 1 << amount
    res = 0
    while dp:  # dp = 0或return 時(shí)循環(huán)結(jié)束
        tmp = 0  # tmp用于臨時(shí)記錄和承接上一個(gè)dp二進(jìn)制
        res += 1  # res為最終答案
        for i in coins:
            # 利用按位右移不斷右移。利用按位或運(yùn)算
            # 將前一次按位右移運(yùn)算與后一次按位右移運(yùn)算合并
            tmp |= dp >> i
        if tmp & 1:  # 當(dāng)tmp最后位數(shù)為1時(shí)res即為答案，返回res
            return res
        dp = tmp
    return -1

位運(yùn)算解法過程我打印出來了，不清楚的可以看看

def coinChange(coins, amount):
    if not amount:
        return 0
    dp = 1 << amount
    res = 0
    while dp:
        print('dp:', bin(dp))
        tmp = 0
        print('tmp:', bin(tmp))
        res += 1
        print('res:', res)
        for i in coins:
            print('i:', i)
            tmp |= dp >> i
            print('ys_tmp:', bin(tmp))
            print('--------------')
        if tmp & 1:
            return res
        dp = tmp
    return -1

輸出

dp: 0b100000000000
tmp: 0b0
res: 1
i: 1
ys_tmp: 0b10000000000
--------------
i: 2
ys_tmp: 0b11000000000
--------------
i: 5
ys_tmp: 0b11001000000
--------------
dp: 0b11001000000
tmp: 0b0
res: 2
i: 1
ys_tmp: 0b1100100000
--------------
i: 2
ys_tmp: 0b1110110000
--------------
i: 5
ys_tmp: 0b1110110010
--------------
dp: 0b1110110010
tmp: 0b0
res: 3
i: 1
ys_tmp: 0b111011001
--------------
i: 2
ys_tmp: 0b111111101
--------------
i: 5
ys_tmp: 0b111111101
--------------