零錢兌換II

力扣題目鏈接(opens new window)

給定不同面額的硬幣和一個(gè)總金額。寫出函數(shù)來(lái)計(jì)算可以湊成總金額的硬幣組合數(shù)。假設(shè)每一種面額的硬幣有無(wú)限個(gè)。

示例 1:

• 輸入: amount = 5, coins = [1, 2, 5]
• 輸出: 4

解釋: 有四種方式可以湊成總金額:

• 5=5
• 5=2+2+1
• 5=2+1+1+1
• 5=1+1+1+1+1

示例 2:

• 輸入: amount = 3, coins = [2]
• 輸出: 0
• 解釋: 只用面額2的硬幣不能湊成總金額3。

示例 3:

• 輸入: amount = 10, coins = [10]
• 輸出: 1

注意，你可以假設(shè)：

• 0 <= amount (總金額) <= 5000
• 1 <= coin (硬幣面額) <= 5000
• 硬幣種類不超過(guò) 500 種
• 結(jié)果符合 32 位符號(hào)整數(shù)

思路

經(jīng)典背包問題

關(guān)鍵字眼：錢幣數(shù)量不限-->完全背包

注意題目要求，本題是要求：可以湊成總金額的硬幣組合數(shù)，是組合個(gè)數(shù)；而單純的完全背包（或者說(shuō)背包問題）要求的是能夠湊成背包的最大價(jià)值

因此，本題屬于背包問題在求排列組合時(shí)的應(yīng)用（那就與目標(biāo)和那題一樣），具體到本題是求組合

組合與排列的區(qū)別

例如示例一：

5 = 2 + 2 + 1

5 = 2 + 1 + 2

這是一種組合，都是 2 2 1。

如果問的是排列數(shù)，那么上面就是兩種排列了。

組合不強(qiáng)調(diào)元素之間的順序，排列強(qiáng)調(diào)元素之間的順序。

詳見：確定遍歷順序（目標(biāo)和）

五步走

1、確定dp數(shù)組含義

dp[j]:能湊成總金額為j的貨幣組合個(gè)數(shù)為dp[j]

對(duì)應(yīng)到題目中，j就是amount，即背包容量

而coins數(shù)組中的元素就是物品

2、確定遞推公式

和目標(biāo)和中的遞推公式完全一樣，這里再簡(jiǎn)要推導(dǎo)一下

推導(dǎo)過(guò)程一切遵循dp數(shù)組含義

假設(shè)amount = 3，即背包容量是3

那么在還沒往里面放東西的時(shí)候，此時(shí)還有3的容量，那么就還能夠有dp[3]種能湊出總金額為3的貨幣組合

若已經(jīng)確定要放入1個(gè)貨幣，那此時(shí)容量就要減1，還剩2個(gè)容量，那么就還能有dp[2]種能湊出總金額為3的貨幣組合

若已經(jīng)確定要放入2個(gè)貨幣，那此時(shí)容量就要減2，還剩1個(gè)容量，那么就還能有dp[1]種能湊出總金額為3的貨幣組合

若已經(jīng)確定要放入3個(gè)貨幣，那此時(shí)容量就要減3，還剩0個(gè)容量，那么就還能有dp[0]種能湊出總金額為3的貨幣組合

從下往上看，以上描述就是將貨幣數(shù)組coins中的物品一個(gè)一個(gè)放入背包的過(guò)程

最后能夠得到dp[3]，因此dp[3]是累加而來(lái)的

所以遞推公式是：dp[j] += dp[j - coins[i]];

3、初始化dp數(shù)組

還是和目標(biāo)和那題一樣，當(dāng)j為0時(shí)，需要初始化為1，也就是說(shuō)，容量為0也有一種組合

dp[0]=1;

其余情況初始化為0，使后面遞推得到的值能夠累加起來(lái)

4、確定遍歷順序

完全背包問題是正序遍歷的；（因?yàn)槲锲凡豢梢灾貜?fù)使用）

01背包問題是倒序遍歷的；（因?yàn)槲锲房梢灾貜?fù)使用）

這里還需要討論一下兩層for循環(huán)中遍歷物品和背包容量先后順序的問題

情況1

情況1：

for(int i = 0; i < coins.size(); ++i){//先遍歷物品
 for(int j = coins[i]; j <= amount; ++i){//再遍歷背包容量
     dp[j] += dp[j - coins[i]];
 }
}

來(lái)模擬一下物品放入，并遍歷背包容量的過(guò)程

假設(shè)amount = 5，coins = [1, 2, 5]

從1開始遍歷，遍歷到2滿足條件，此時(shí)組合為{1,2}，這種順序下不會(huì)遍歷得到{2,1}，因?yàn)?永遠(yuǎn)在1后面被用來(lái)嘗試放入背包

所以先物品后容量的順序得到的是物品放入背包的組合數(shù)

這么說(shuō)可能有點(diǎn)抽象，我其實(shí)一直不清楚：為什么第二層for循環(huán)中循環(huán)變量的初始值是coins[i]，以及為什么每輪循環(huán)后其都要遞增

所以嘗試模擬推導(dǎo)一下dp數(shù)組:

    0  1  2  3  4  5(背包容量)
    1  0  0  0  0  0 (沒有硬幣的時(shí)候）
=======================
    0  1  2  3  4  5(背包容量)
1   1  1  1  1  1  1
=======================
    0  1  2  3  4  5(背包容量)
1   1  1  1  1  1  1
2         2  2  3  3
有了面值為2的硬幣后，哎，我就是不用，所以方案數(shù)還是dp[j]種；
但是我如果用了，那我看看在放入這枚硬幣前，也就是背包容量為[j-coins[i]]的時(shí)候有幾種方案;
兩種情況加起來(lái)，所以就是  dp[j] = dp[j]+dp[j-coins[i]];
========================
    0  1  2  3  4  5(背包容量)
1   1  1  1  1  1  1
2         2  2  3  3
5                  4

上述解釋摘自https://leetcode.cn/problems/coin-change-ii/solution/gong-shui-san-xie-xiang-jie-wan-quan-bei-6hxv/979973

這里解釋了為什么第二層for循環(huán)每次都要從coins[i]開始遍歷

拿coins[1]，即2來(lái)舉例，硬幣面值是2，那背包容量為0和1時(shí)自然不可能放下，所以至少要等背包容量大于等于2時(shí)才能考慮使用面值為2的硬幣

而當(dāng)?shù)诙觙or循環(huán)的循環(huán)變量以coins[1]為初始值時(shí)，就意味著要開始找面值為2的硬幣放入背包的組合有幾種了

還是拿上面的來(lái)看，當(dāng)有了面值為2的硬幣后，如果背包容量大于等于2，那么可以用面值為2的硬幣配合之前獲得的面值為1的硬幣來(lái)組合出當(dāng)前背包容量（面值）。

這件事情怎么說(shuō)會(huì)比較好呢？

也就是說(shuō)，如果我們現(xiàn)在有了面值為2的硬幣，那么在湊容量大于2的背包時(shí)就可以用這個(gè)面值的硬幣配合之前面值的硬幣來(lái)湊出背包容量

但是，實(shí)際上不用面值為2的硬幣我們也能用之前的硬幣湊出對(duì)應(yīng)的背包容量

只是說(shuō)用了新面值的硬幣之后，湊出背包容量的組合數(shù)量就增加了

當(dāng)只有面值為1的硬幣時(shí)，要湊背包容量2，只有一種組合：1、1；

當(dāng)有面值為1、2的硬幣時(shí)，除了1、1以外，還可以有2，組合數(shù)量增加為2；其他背包容量以此類推

聯(lián)系dp數(shù)組的含義dp[j]表示能湊成總金額為j的貨幣組合個(gè)數(shù)為dp[j]

那dp[2]就是能湊出總金額為2的貨幣組合個(gè),

我們用面值為1的硬幣也能湊出來(lái)總金額2，且組合有1+1+1+1+1=5種，即dp[1]；

在此基礎(chǔ)上加入面值為2的硬幣，也能湊出總金額2，組合數(shù)量在上面的基礎(chǔ)上增加1+1+2+2+3+3=10種，即dp[2]

所以，dp[2] = dp[2] + dp[1];

這就和遞推公式dp[j] += dp[j - coins[i]];對(duì)應(yīng)上了

回到最開始的疑問，為什么第二層for循環(huán)每次都要從coins[i]開始遍歷

現(xiàn)在能夠理解了，其實(shí)就是為了分開計(jì)算組合的情況，從coins[i]開始之后計(jì)算得到的dp數(shù)組的值（也就是組合種類），是包含了使用當(dāng)前新加入的coins[i]面值的硬幣之后的組合種類

而代碼就是在模擬這個(gè)操作，至于j為什么每次都要遞增。

因?yàn)?strong>j其實(shí)只是在遍歷背包容量時(shí)的一個(gè)指針，j的遞增跟coins[i]沒有關(guān)系

情況2

情況2：

for(int j = 0; j <= amount; ++j){//先遍歷背包容量
 for(int i = 0; i < coins.size(); ++i){//再遍歷物品
     if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
 }
}

還是模擬一下，

遍歷背包容量0，都放不下

遍歷背包容量1，可以放一個(gè)1，此時(shí)能夠湊齊容量的集合有：{1}

遍歷背包容量2，此時(shí)coins中的1和2都可以放入，此時(shí)能夠湊齊容量的集合有：{1,1}、{2}

遍歷背包容量3，此時(shí)coins中的1和2都可以放入，此時(shí)能夠湊齊容量的集合有：{1,1,1}、{1,2}、{2,1}

...之后的集合以此類推

為什么這里會(huì)出現(xiàn){1,2}、{2,1}，因?yàn)橄缺闅v背包容量時(shí)，相當(dāng)于拿背包容量去嘗試套硬幣的面值

此時(shí)我們是默認(rèn)有所有面值的硬幣的，因此一旦有能夠用背包容量套下的硬幣集合，那么該集合的所有方式都會(huì)被遍歷出來(lái)

因此，先容量后物品的順序得到的是物品放入背包的排列數(shù)

代碼

代碼其實(shí)就是按照模板寫就好了，其中比較"細(xì)思恐極"的部分再上面已經(jīng)詳細(xì)解釋了

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        //定義并初始化dp數(shù)組
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        //遍歷dp數(shù)組
        for(int i = 0; i < coins.size(); ++i){//遍歷物品
            //第二層for中循環(huán)變量的初始值j是第一層for循環(huán)遍歷到的物品的重量（容量）
            //用于定位到大于等于當(dāng)前新加入硬幣面值的背包容量位置
            for(int j = coins[i]; j <= amount; ++j){//遍歷背包容量
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

組合總和IV

力扣題目鏈接(opens new window)

難度：中等

給定一個(gè)由正整數(shù)組成且不存在重復(fù)數(shù)字的數(shù)組，找出和為給定目標(biāo)正整數(shù)的組合的個(gè)數(shù)。

示例:

• nums = [1, 2, 3]
• target = 4

所有可能的組合為： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

請(qǐng)注意，順序不同的序列被視作不同的組合。

因此輸出為 7。

思路

題目給的示例中有一個(gè)注意事項(xiàng)，"順序不同的序列被視作不同的組合"

也就是說(shuō)，本題要求的是排列而不是組合（求組合的完全背包可以看 零錢兌換II）

根據(jù)之前題目的分析可以知道，dp數(shù)組的遍歷順序會(huì)影響所求的結(jié)果

先物品后容量，得到的是組合；

先容量后物品，得到的是排列；

代碼

本題五步走分析和之前的完全背包是一樣的，包括dp數(shù)組的含義也都是一樣的，直接來(lái)看代碼就行

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        //定義dp數(shù)組
        vector<int> dp(target + 1, 0);
        //初始化
        dp[0] = 1;
        //遍歷dp數(shù)組
        for(int j = 0; j <= target; ++j){//先遍歷物品
            for(int i = 0; i < nums.size(); ++i){//后遍歷背包容量
                if(j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]]) dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

一些解釋：

1、j - nums[i] >= 0

拓展：本題與爬樓梯的聯(lián)系

回憶一下 爬樓梯 ，本題的要求是我們一步可以爬1個(gè)或2個(gè)臺(tái)階，問爬到樓頂（也就是n個(gè)臺(tái)階）一共有幾種方法

如果題目條件變一下，一步可以爬3個(gè)臺(tái)階、4個(gè)、m個(gè)呢？

那其實(shí)“一步可以爬幾個(gè)臺(tái)階”，“幾個(gè)臺(tái)階”就相當(dāng)于本題nums數(shù)組中的元素，即物品

如果是一步可以爬3個(gè)臺(tái)階，那就是數(shù)組從1到3

假設(shè)爬到樓頂有n階樓梯，那這個(gè)n就是target，即背包容量

而我們要求的就是所有爬到樓頂方法的排列（假設(shè)n=3，先爬1步再爬2步和先爬2步再爬1步顯然是兩種不同的上樓方法）文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-418264.html

到了這里，關(guān)于【LeetCode動(dòng)態(tài)規(guī)劃#08】完全背包問題實(shí)戰(zhàn)與分析（零錢兌換II--求組合、組合總和IV--求排列）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！