第Python零錢兌換的實現(xiàn)代碼目錄題目：題目分析：解題思路：解法一：遞歸代碼實現(xiàn)代碼注釋解法二：

題目：

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

計算并返回可以湊成總金額所需的最少的硬幣個數(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

題目分析：

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

解題思路：

解法一：遞歸

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

1.分析確定dp數(shù)組以及其下標(biāo)的含義或狀態(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ù)。那么當(dāng)金額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ù)組

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

4.確定遍歷的順序

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

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

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

代碼實現(xiàn)

defcoinChange(coins,amount):

dp=[float('inf')]*(amount+1)

dp[0]=0

forcoinincoins:

foriinrange(coin,amount+1):

dp[i]=min(dp[i],dp[i-coin]+1)

returndp[amount]ifdp[amount]!=float('inf')else-1

代碼注釋

defcoinChange(coins,amount):

#初始化dp列表

dp=[float('inf')]*(amount+1)

dp[0]=0#初始化遞推公式基礎(chǔ)

forcoinincoins:#遍歷硬幣

#遍歷尋找構(gòu)成amount最優(yōu)解

foriinrange(coin,amount+1):

dp[i]=min(dp[i],dp[i-coin]+1)

#如果最終沒有找到湊成amount金額的硬幣，返回-1

returndp[amount]ifdp[amount]!=float('inf')else-1

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

解法二：

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

代碼實現(xiàn)

defcoinChange(coins,amount):

ifnotamount:

return0

dp=1amount

res=0

whiledp:

tmp=0

res+=1

foriincoins:

tmp|=dpi

iftmp1:

returnres

dp=tmp

return-1

代碼注釋

defcoinChange(coins,amount):

ifnotamount:

return0

#按位左移運算構(gòu)造類似dp數(shù)組的記錄二進(jìn)制

dp=1amount

res=0

whiledp:#dp=0或return時循環(huán)結(jié)束

tmp=0#tmp用于臨時記錄和承接上一個dp二進(jìn)制

res+=1#res為最終答案

foriincoins:

#利用按位右移不斷右移。利用按位或運算

#將前一次按位右移運算與后一次按位右移運算合并

tmp|=dpi

iftmp1:#當(dāng)tmp最后位數(shù)為1時res即為答案，返回res

returnres

dp=tmp

return-1

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

defcoinChange(coins,amount):

ifnotamount:

return0

dp=1amount

res=0

whiledp:

print('dp:',bin(dp))

tmp=0

print('tmp:',bin(tmp))

res+=1

print('res:',res)

foriincoins:

print('i:',i)

tmp|=dpi

print('ys_tmp:',bin(tmp))

print('--------------')

iftmp1:

returnres

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: