快捷導(dǎo)航

Python動(dòng)態(tài)規(guī)劃之零錢兌換問(wèn)題詳解

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

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

問(wèn)題描述

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

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

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

問(wèn)題分析

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

是否求最值？顯而易見，這是一個(gè)求最小值的問(wèn)題；

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

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

求解套路

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

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

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

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

代碼

def coin_change(coins,amount):

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

    # 初始化dp數(shù)組，長(zhǎng)度是amount+1，因?yàn)?~n一共有n+1個(gè)元素
    dp = [amount+1]*(amount+1)
    # 因?yàn)閐p[n]要靠dp[0]推導(dǎo)，所以dp[0]需要按實(shí)際情況初始化為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: # 若為真，說(shuō)明無(wú)解
        return -1
    else:
        return dp[amount]


if __name__ == '__main__':
	
    # 測(cè)試用例，來(lái)自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ù)雜度分析

時(shí)間復(fù)雜度

顯然是O(nm)，其中n為amount，即總金額，m為硬幣coins的種類。

空間復(fù)雜度

由于我們使用長(zhǎng)度為amount+1的數(shù)組dp來(lái)保存狀態(tài)，因此為O(n)。

到此這篇關(guān)于Python動(dòng)態(tài)規(guī)劃之零錢兌換問(wèn)題詳解的文章就介紹到這了,更多相關(guān)Python零錢兌換問(wèn)題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: