題目：

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

計算并返回可以湊成總金額所需的 最少的硬幣個數(shù) 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。你可以認為每種硬幣的數(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

題目分析：

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

解題思路：

解法一：遞歸

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

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

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

2.確定遞推公式 

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

那為什么要+1呢？

這里我們明確dp[i - coins[i]]是湊夠金額 i - coin[i]的最少硬幣個數(shù)。那么當金額i - coin[i]變到 i 時，意味著我們在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ù)組

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

4.確定遍歷的順序

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

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

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

代碼實現(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  # 初始化遞推公式基礎
    for coin in coins:   # 遍歷硬幣
        # 遍歷尋找構成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

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

解法二：

接下來就是玄學位運算了。先看代碼

代碼實現(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
    # 按位左移運算構造類似dp數(shù)組的記錄二進制
    dp = 1 << amount
    res = 0
    while dp:  # dp = 0或return 時循環(huán)結束
        tmp = 0  # tmp用于臨時記錄和承接上一個dp二進制
        res += 1  # res為最終答案
        for i in coins:
            # 利用按位右移不斷右移。利用按位或運算
            # 將前一次按位右移運算與后一次按位右移運算合并
            tmp |= dp >> i
        if tmp & 1:  # 當tmp最后位數(shù)為1時res即為答案，返回res
            return res
        dp = tmp
    return -1

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

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
--------------

雖然難理解，但是解題效率不是一般的高

時間復雜度O(n),n為coins長度?？臻g復雜度O(1),使用有限變量。

到此這篇關于Python零錢兌換的實現(xiàn)代碼的文章就介紹到這了,更多相關Python零錢兌換內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論