快捷導(dǎo)航

Python動態(tài)規(guī)劃之零錢兌換問題詳解

更新時間：2023年11月03日 09:44:43 作者：驚瑟

這篇文章主要介紹了Python動態(tài)規(guī)劃之零錢兌換問題詳解,這次我們就按照套路模板,再來剖析一道經(jīng)典動規(guī)題目零錢兌換,計算并返回可以湊成總金額所需的最少的硬幣個數(shù) 如果沒有任何一種硬幣組合能組成總金額,返回-1,需要的朋友可以參考下

問題描述

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

計算并返回可以湊成總金額所需的最少的硬幣個數(shù) 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認(rèn)為每種硬幣的數(shù)量是無限的。

問題分析

考察其是否滿足動態(tài)規(guī)劃的兩個特征：

是否求最值？顯而易見，這是一個求最小值的問題；

是否具有最優(yōu)子結(jié)構(gòu)？考察大規(guī)模問題的解是否可以由小規(guī)模問題的解推導(dǎo)出來。我們可以假設(shè)amount<n所需的最小硬幣數(shù)量都是已知的，那如何得出amount=n所需的最小硬幣數(shù)量呢？可以結(jié)合具體場景，如果你手上有1塊、2塊面額的硬幣，要求湊出總額amount =5的所需最小硬幣個數(shù)，而amount <5的所需最小硬幣個數(shù)是已知的。很容易想到，只需要在amount =3或者amount =4的所需最小硬幣個數(shù)的基礎(chǔ)上再加1個硬幣（2塊或者1塊）就可以得到amount =5所需的硬幣個數(shù)了（注意，這里還不是最小硬幣個數(shù)），再取這兩種情況的最小值，便可以得到amount =5的所需的最小硬幣個數(shù)了（是不是想起了跳臺階問題？）。

以上分析我們可以得出，該問題是動態(tài)規(guī)劃問題。

求解套路

明確有哪些狀態(tài)。很容易想到，在狀態(tài)轉(zhuǎn)化過程（大規(guī)模問題由小問題規(guī)模問題推導(dǎo)的過程）中，總金額amount 一定是發(fā)生變化的，因此amount 是狀態(tài)。

明確dp數(shù)組含義。根據(jù)求什么設(shè)什么原則，我們可以設(shè)dp代表最少硬幣數(shù)量，由于只有amount一個狀態(tài)，因此dp為1維。綜上，dp應(yīng)設(shè)為dp[n]，代表湊出總額為n需要的最少數(shù)量金幣。

狀態(tài)轉(zhuǎn)移方程。有了【問題分析】中的例子，相信找出狀態(tài)轉(zhuǎn)移方程并不難，直接貼結(jié)論：

初始化dp。由于求的是最小值，因此要反著來，初始化為最大。考慮到coins是正整數(shù)數(shù)組，即coin最小是1，所以對于總金額n，最壞情況下（即只用面值為1的硬幣）需要n個硬幣。我們需要將dp初始化為正常情況下取不到的值，因此我們將dp其初始化為n+1。

代碼

def coin_change(coins,amount):

    # 判斷邊界值
    if amount == 0:
        return 0

    # 初始化dp數(shù)組，長度是amount+1，因為0~n一共有n+1個元素
    dp = [amount+1]*(amount+1)
    # 因為dp[n]要靠dp[0]推導(dǎo)，所以dp[0]需要按實際情況初始化為0
    dp[0] = 0

    # 遍歷狀態(tài)
    for i in range(1,amount+1):
        # 注意coins并不是狀態(tài)，只是我們狀態(tài)轉(zhuǎn)移方程需要遍歷它取最小值
        for coin in coins:
            if i-coin >= 0:
                dp[i] = min(dp[i],dp[i-coin]+1)
    if dp[amount] == amount+1: # 若為真，說明無解
        return -1
    else:
        return dp[amount]


if __name__ == '__main__':
	
    # 測試用例，來自leecode #322題
    eg =[[[1,2,5],11],[[2],3],[[1],0],[[1],1],[[1],2]]
    for coins,amount in eg:
        print(coin_change(coins,amount),end='  ')

算法復(fù)雜度分析