這篇page是針對(duì)leetcode上的322.零錢(qián)兌換所寫(xiě)的。小尼先簡(jiǎn)單的說(shuō)明一下這道題的意思，給出一個(gè)整數(shù)數(shù)組coins，表示不同面額的硬幣，以及一個(gè)整數(shù)amount，表示總金額。需要計(jì)算并且返回可以湊成總金額所需的最少的硬幣個(gè)數(shù)，如果湊不出來(lái)，就直接返回-1.

其實(shí)這道題就是一道典型的完全背包問(wèn)題，因?yàn)槲覀兊挠矌诺慕痤~可以多次使用，并且我們這里給出需要達(dá)到的金額數(shù)就是對(duì)應(yīng)我們完全背包里面的背包的容量。接下來(lái)，小尼說(shuō)明一下這道題的金額的解法：

1、確定dp數(shù)組以及下標(biāo)的含義：dp[j]就是表示湊足總額為j所需錢(qián)幣的最小個(gè)數(shù)

2、確定遞推公式：得到dp[j]，就只有一個(gè)來(lái)源，dp[j - coins[i]]，我們所取的遞推公式就是：

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

3、dp數(shù)組如何初始化：我們應(yīng)該知道湊足總金額為0所需錢(qián)幣的個(gè)數(shù)一定是0，那么我們可以得出dp[0]? = 0

4、確定遍歷順序：其實(shí)因?yàn)榇祟}球的是錢(qián)幣的最小的個(gè)數(shù)，所以遍歷的順序就不想完全背包問(wèn)題那么寫(xiě)死，也就是說(shuō)此題并不強(qiáng)調(diào)是排列還是組合，所以本題小尼采取的就是外層for遍歷物品，內(nèi)存for遍歷背包

5、最后就是我們需要導(dǎo)出dp數(shù)組

接下來(lái)小尼拉一下這道題的解題的代碼：

class Solution {public int coinChange(int[] coins, int amount) {int max = Integer.MAX_VALUE;int[] dp = new int[amount + 1];for(int j = 0; j < dp.length; j++){dp[j] = max;}dp[0] = 0;for(int i = 0; i < coins.length; i++){for(int j = coins[i]; j <= amount; j++){if(dp[j - coins[i]] != max){dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}return dp[amount] == max ? -1 : dp[amount];} }

小尼在這道題一開(kāi)始其實(shí)是充滿了疑惑，怎么感覺(jué)這道題跟0-1背包的解法和相似遍歷條件與0-1背包的寫(xiě)法及其形似，但是小尼一定需要說(shuō)明一點(diǎn)，在這里我們的內(nèi)層for循環(huán)是從coins[i]開(kāi)始進(jìn)行的，而在0-1背包中內(nèi)層的for循環(huán)確實(shí)從tatget開(kāi)始進(jìn)行的，這里也就是為什么0-1背包問(wèn)題里面的物品只使用了一次，而這里面的物品確實(shí)多次使用，其實(shí)就是我們這里面的物品是在不斷的依靠前面本層上一次dp數(shù)組的放入的數(shù)目進(jìn)行對(duì)應(yīng)的疊加的，但是我們0-1背包里面的數(shù)據(jù)只是根據(jù)我們上一層循環(huán)里面的數(shù)據(jù)進(jìn)行疊加。

希望上面的代碼可以幫助到小伙伴們~~~

總結(jié)

以上是生活随笔為你收集整理的My Seventy-seventh Page - 零钱兑换 - By Nicolas的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。