算法相關(guān)數(shù)據(jù)結(jié)構(gòu)總結(jié)：

前面整理了01背包，在leetcode題庫(kù)中主要就是01背包和完全背包問(wèn)題，所以在這里整理一下完全背包的知識(shí)點(diǎn)。

一、完全背包問(wèn)題

有N件物品和一個(gè)最多能背重量為W的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i] 。每件物品都有無(wú)限個(gè)（也就是可以放入背包多次），求解將哪些物品裝入背包里物品價(jià)值總和最大。

完全背包和01背包問(wèn)題唯一不同的地方就是，每種物品有無(wú)限件。

注：leetcode上沒(méi)有純完全背包問(wèn)題，都是需要完全背包的各種應(yīng)用，需要轉(zhuǎn)化成完全背包問(wèn)題。

01背包和完全背包唯一不同就是體現(xiàn)在遍歷順序上，所以針對(duì)遍歷順序進(jìn)行分析。其它動(dòng)規(guī)五部曲參考01背包。

二、完全背包遍歷順序

首先回顧一下01背包的遍歷順序：

for(int i = 0; i < weight.size(); i++) { // 遍歷物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

我們知道01背包內(nèi)嵌的循環(huán)是從大到小遍歷，為了保證每個(gè)物品僅被添加一次。

而完全背包的物品是可以添加多次的，所以要從小到大去遍歷，即：

// 先遍歷物品，再遍歷背包
int[] dp = new int[bagWeight + 1];
for (int i = 0; i < weight.length; i++){
    for (int j = 1; j <= bagWeight; j++){
        if (j - weight[i] >= 0){
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
}

為什么遍歷物品在外層循環(huán)，遍歷背包容量在內(nèi)層循環(huán)？

在01背包中二維dp數(shù)組的兩個(gè)for遍歷的先后循序是可以顛倒，一維dp數(shù)組的兩個(gè)for循環(huán)先后循序一定是先遍歷物品，再遍歷背包容量。

在完全背包中，對(duì)于一維dp數(shù)組來(lái)說(shuō)，其實(shí)兩個(gè)for循環(huán)嵌套順序同樣無(wú)所謂。

因?yàn)?code>dp[j] 是根據(jù) 下標(biāo)j之前所對(duì)應(yīng)的dp[j]計(jì)算出來(lái)的。 只要保證下標(biāo)j之前的dp[j]都是經(jīng)過(guò)計(jì)算的就可以。完全背包中，兩個(gè)for循環(huán)的先后循序，都不影響計(jì)算dp[j]所需要的值。

先遍歷被背包在遍歷物品，代碼如下：

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

注：全文說(shuō)的都是對(duì)于純完全背包問(wèn)題，其for循環(huán)的先后循環(huán)是可以顛倒的！但如果題目稍稍有點(diǎn)變化，就會(huì)體現(xiàn)在遍歷順序上。

如果問(wèn)裝滿背包有幾種方式的話？ 那么兩個(gè)for循環(huán)的先后順序就有很大區(qū)別了，而leetcode上的題目都是這種稍有變化的類型。這些將根據(jù)具體的題目進(jìn)行分析。

三、leetcode例題講解完全背包問(wèn)題

518. 零錢兌換 II

leetcode題目鏈接：518. 零錢兌換 II

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

請(qǐng)你計(jì)算并返回可以湊成總金額的硬幣組合數(shù)。如果任何硬幣組合都無(wú)法湊出總金額，返回 0 。

假設(shè)每一種面額的硬幣有無(wú)限個(gè)。

示例一：

輸入：amount = 5, coins = [1, 2, 5]
輸出：4
解釋：有四種方式可以湊成總金額：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例二：

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

示例三：

輸入：amount = 10, coins = [10] 
輸出：1

這是一道典型的背包問(wèn)題，一看到錢幣數(shù)量不限，就知道這是一個(gè)完全背包。

但本題和純完全背包不一樣，純完全背包是能否湊成總金額，而本題是要求湊成總金額的個(gè)數(shù)！

然后就是組合數(shù)：組合不強(qiáng)調(diào)元素之間的順序，排列強(qiáng)調(diào)元素之間的順序。

1.確定dp數(shù)組以及下標(biāo)的含義

dp[i]：湊成總金額i的貨幣組合數(shù)為dp[i]

2.確定遞推公式

dp[i] （考慮coins[j]的組合總和） 就是所有的dp[i - coins[j]]（不考慮coins[j]）相加。

所以遞推公式：dp[i] += dp[i - coins[j]]; 和01背包相同。

3.dp數(shù)組如何初始化

dp[0]一定要為1，dp[0] = 1是 遞歸公式的基礎(chǔ)。

從dp[i]的含義上來(lái)講就是，湊成總金額0的貨幣組合數(shù)為1。

下標(biāo)非0的dp[j]初始化為0，這樣累計(jì)加dp[i - coins[j]]的時(shí)候才不會(huì)影響真正的dp[i]

4.確定遍歷順序

本題是外層for循環(huán)遍歷物品（錢幣），內(nèi)層for遍歷背包（金錢總額），還是外層for遍歷背包（金錢總額），內(nèi)層for循環(huán)遍歷物品（錢幣）呢？

在上面講解了完全背包的兩個(gè)for循環(huán)的先后順序都是可以的。但本題就不行了。

因?yàn)?strong>純完全背包求得是能否湊成總和，和湊成總和的元素有沒(méi)有順序沒(méi)關(guān)系，即：有順序也行，沒(méi)有順序也行！

而本題要求湊成總和的組合數(shù)，元素之間要求沒(méi)有順序。

所以純完全背包是能湊成總和就行，不用管怎么湊的。

本題是求湊出來(lái)的方案?jìng)€(gè)數(shù)，且每個(gè)方案?jìng)€(gè)數(shù)是為組合數(shù)。

先來(lái)看 外層for循環(huán)遍歷物品（錢幣），內(nèi)層for遍歷背包（金錢總額）的情況。

舉例用的dp[j] += dp[j - coins[i]]; 這里就不再改了。

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

假設(shè)：coins[0] = 1，coins[1] = 5。

那么就是先把1加入計(jì)算，然后再把5加入計(jì)算，得到的方法數(shù)量只有{1, 5}這種情況。而不會(huì)出現(xiàn){5, 1}的情況。

這種遍歷順序中dp[j]里計(jì)算的是組合數(shù)！

另外一種遍歷順序：

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]];
    }
}

背包容量的每一個(gè)值，都是經(jīng)過(guò) 1 和 5 的計(jì)算，包含了{(lán)1, 5} 和 {5, 1}兩種情況。

此時(shí)dp[j]里算出來(lái)的就是排列數(shù)！

5.舉例推導(dǎo)dp數(shù)組

省略。

Java代碼實(shí)現(xiàn)：

class Solution {
    public int change(int amount, int[] coins) {
        // 動(dòng)態(tài)規(guī)劃，dp[i]表示湊成金額i的硬幣組合數(shù)
        // dp[i] += dp[i - coins[j]]
        // dp[0] = 1
        // 遍歷順序：本題先循環(huán)錢幣，后循環(huán)金錢總額，否則就會(huì)有重復(fù){1，5}和{5，1}就成了兩種方法
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int j = 0; j < coins.length; j++){
            for(int i = coins[j]; i <= amount; i++){
                    dp[i] += dp[i - coins[j]];
            }
        }
        return dp[amount];
    }
}

377. 組合總和 Ⅳ

leetcode題目鏈接：377. 組合總和 Ⅳ

給你一個(gè)由 不同 整數(shù)組成的數(shù)組 nums ，和一個(gè)目標(biāo)整數(shù) target 。請(qǐng)你從 nums 中找出并返回總和為 target 的元素組合的個(gè)數(shù)。

示例一：

輸入：nums = [1,2,3], target = 4
輸出：7
解釋：
所有可能的組合為：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
請(qǐng)注意，順序不同的序列被視作不同的組合。

示例二：

輸入：nums = [9], target = 3
輸出：0

本題題目描述說(shuō)是求組合，但又說(shuō)是可以元素相同順序不同的組合算兩個(gè)組合，其實(shí)就是求排列！

組合不強(qiáng)調(diào)順序，(1,5)和(5,1)是同一個(gè)組合。

排列強(qiáng)調(diào)順序，(1,5)和(5,1)是兩個(gè)不同的排列。

但其本質(zhì)是本題求的是排列總和，而且僅僅是求排列總和的個(gè)數(shù)，并不是把所有的排列都列出來(lái)。

1.確定dp數(shù)組以及下標(biāo)的含義

dp[i]: 湊成目標(biāo)正整數(shù)為i的排列個(gè)數(shù)為dp[i]

2.確定遞推公式

dp[i]（考慮nums[j]）可以由 dp[i - nums[j]]（不考慮nums[j]） 推導(dǎo)出來(lái)。

因?yàn)橹灰玫絥ums[j]，排列個(gè)數(shù)dp[i - nums[j]]，就是dp[i]的一部分。

所以遞推公式：dp[i] += dp[i - nums[j]]; 和01背包相同。

3.dp數(shù)組如何初始化

因?yàn)檫f推公式dp[i] += dp[i - nums[j]]的緣故，dp[0]要初始化為1，這樣遞歸其他dp[i]的時(shí)候才會(huì)有數(shù)值基礎(chǔ)。

其實(shí)沒(méi)有意義，所以我也不去強(qiáng)行解釋它的意義了，因?yàn)轭}目中也說(shuō)了：給定目標(biāo)值是正整數(shù)！ 所以dp[0] = 1是沒(méi)有意義的，僅僅是為了推導(dǎo)遞推公式。

至于非0下標(biāo)的dp[i]應(yīng)該初始為多少呢？

初始化為0，這樣才不會(huì)影響dp[i]累加所有的dp[i - nums[j]]。

4.確定遍歷順序

個(gè)數(shù)可以不限使用，說(shuō)明這是一個(gè)完全背包。

得到的集合是排列，說(shuō)明需要考慮元素之間的順序。

如果求排列數(shù)就是外層for遍歷背包，內(nèi)層for循環(huán)遍歷物品。

如果把遍歷nums（物品）放在外循環(huán)，遍歷target的作為內(nèi)循環(huán)的話，舉一個(gè)例子：計(jì)算dp[4]的時(shí)候，結(jié)果集只有 {1,3} 這樣的集合，不會(huì)有{3,1}這樣的集合，因?yàn)閚ums遍歷放在外層，3只能出現(xiàn)在1后面！

所以本題遍歷順序最終遍歷順序：target（背包）放在外循環(huán)，將nums（物品）放在內(nèi)循環(huán)，內(nèi)循環(huán)從前到后遍歷。

5.舉例推導(dǎo)dp數(shù)組

省略。

Java代碼實(shí)現(xiàn)：

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 動(dòng)態(tài)規(guī)劃，完全背包，dp[i] 表示返回元素總和i的元素組合個(gè)數(shù)
        // dp[i] += dp[i - nums[j]]
        // dp[0] = 1
        // 遍歷順序也需要考慮，對(duì)于每一個(gè)元素和來(lái)說(shuō)，遍歷加每一個(gè)小于和的元素，先遍歷背包，再遍歷物品
        // 雖說(shuō)是組合問(wèn)題，但(1, 1, 2)，(1, 2, 1)，(2, 1, 1)是三種組合，所以與一般組合問(wèn)題不同
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i = 0; i <= target; i++){  // 遍歷背包
            for(int j = 0; j < nums.length; j++){  // 遍歷物品
                if(i >= nums[j]){
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}

322. 零錢兌換

leetcode題目鏈接：322. 零錢兌換
給你一個(gè)整數(shù)數(shù)組 coins ，表示不同面額的硬幣；以及一個(gè)整數(shù) amount ，表示總金額。

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

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

示例一：

輸入：coins = [1, 2, 5], amount = 11
輸出：3 
解釋：11 = 5 + 5 + 1

示例二：

輸入：coins = [2], amount = 3
輸出：-1

示例三：

輸入：coins = [1], amount = 0
輸出：0

這道題還是零錢兌換，但套路不一樣。

題目中說(shuō)每種硬幣的數(shù)量是無(wú)限的，可以看出是典型的完全背包問(wèn)題。

1.確定dp數(shù)組以及下標(biāo)的含義

dp[i]：湊足總額為i所需錢幣的最少個(gè)數(shù)為dp[i]

2.確定遞推公式

得到dp[i]（考慮coins[j]），只有一個(gè)來(lái)源，dp[i - coins[j]]（沒(méi)有考慮coins[j]）。

湊足總額為i - coins[j]的最少個(gè)數(shù)為dp[i - coins[j]]，那么只需要加上一個(gè)錢幣coins[j]即dp[i - coins[j]] + 1就是dp[i]（考慮coins[j]）

所以dp[j] 要取所有 dp[i - coins[j]] + 1 中最小的。

遞推公式：dp[i] = min(dp[i - coins[j]] + 1, dp[i]);

3.dp數(shù)組如何初始化

首先湊足總金額為0所需錢幣的個(gè)數(shù)一定是0，那么dp[0] = 0;

其他下標(biāo)對(duì)應(yīng)的數(shù)值呢？

考慮到遞推公式的特性，dp[j]必須初始化為一個(gè)最大的數(shù)，否則就會(huì)在min(dp[i - coins[j]] + 1, dp[i])比較的過(guò)程中被初始值覆蓋。

所以下標(biāo)非0的元素都是應(yīng)該是最大值。

注：計(jì)算min，初始化是最大值，計(jì)算max初始化是0。

4.確定遍歷順序

本題求錢幣最小個(gè)數(shù)，那么錢幣有順序和沒(méi)有順序都可以，都不影響錢幣的最小個(gè)數(shù)。。

所以本題并不強(qiáng)調(diào)集合是組合還是排列。

所以本題的兩個(gè)for循環(huán)的關(guān)系是：外層for循環(huán)遍歷物品，內(nèi)層for遍歷背包或者外層for遍歷背包，內(nèi)層for循環(huán)遍歷物品都是可以的！

5.舉例推導(dǎo)dp數(shù)組

省略。

Java代碼實(shí)現(xiàn)：

class Solution {
    // int minCount = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        // 動(dòng)態(tài)規(guī)劃 dp[i] 表示組成金額i所需最少的硬幣數(shù)量，典型的完全背包問(wèn)題
        if(amount == 0) return 0;
        int[] dp = new int[amount+1]; 
        Arrays.fill(dp, amount+1);  // 也可以直接填充Integer.MAX_VALUE
        dp[0] = 0;
        for(int i = 1; i < amount+1; i++){  // 數(shù)量，遍歷背包
            for(int j = 0; j < coins.length; j++){  // 金額，遍歷物品
                // 最小硬幣數(shù) = 最小硬幣數(shù)與該金額減去一個(gè)面值的最小硬幣數(shù)+1
                if(coins[j] <= i){
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
}

279. 完全平方數(shù)

leetcode題目鏈接：279.完全平方數(shù)

給定正整數(shù) n，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, …）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少。

給你一個(gè)整數(shù) n ，返回和為 n 的完全平方數(shù)的 最少數(shù)量 。

完全平方數(shù) 是一個(gè)整數(shù)，其值等于另一個(gè)整數(shù)的平方；換句話說(shuō)，其值等于一個(gè)整數(shù)自乘的積。例如，1、4、9 和 16 都是完全平方數(shù)，而 3 和 11 不是。

示例一：

輸入：n = 12
輸出：3 
解釋：12 = 4 + 4 + 4

示例二：

輸入：n = 13
輸出：2
解釋：13 = 4 + 9

把題目翻譯一下：完全平方數(shù)就是物品（可以無(wú)限件使用），湊個(gè)正整數(shù)n就是背包，問(wèn)湊滿這個(gè)背包最少有多少物品？

這樣就回到了熟悉的完全背包問(wèn)題。

1.確定dp數(shù)組以及下標(biāo)的含義

dp[i]：和為i的完全平方數(shù)的最少數(shù)量為dp[i]

2.確定遞推公式

dp[i] 可以由dp[i - j * j]推出， dp[i - j * j] + 1 便可以湊成dp[j]。

此時(shí)我們要選擇最小的dp[j]，所以遞推公式：dp[i] = min(dp[i - j * j] + 1, dp[i]);

3.dp數(shù)組如何初始化

dp[0]表示 和為0的完全平方數(shù)的最小數(shù)量，那么dp[0]一定是0。

題目描述，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, …），題目描述中可沒(méi)說(shuō)要從0開(kāi)始，dp[0]=0完全是為了遞推公式。

非0下標(biāo)的dp[i]應(yīng)該是多少呢？

從遞歸公式dp[i] = min(dp[i - j * j] + 1, dp[i]);中可以看出每次dp[j]都要選最小的，所以非0下標(biāo)的dp[i]一定要初始為最大值，這樣dp[i]在遞推的時(shí)候才不會(huì)被初始值覆蓋。

4.確定遍歷順序

本題的兩個(gè)for循環(huán)的關(guān)系是：外層for循環(huán)遍歷物品，內(nèi)層for遍歷背包或者外層for遍歷背包，內(nèi)層for循環(huán)遍歷物品都是可以的！

5.舉例推導(dǎo)dp數(shù)組

省略。

Java代碼實(shí)現(xiàn)：

class Solution {
    public int numSquares(int n) {
        // 動(dòng)態(tài)規(guī)劃，完全背包
        // dp[i] 表示和為i的完全平方數(shù)的最小數(shù)量
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1; i <= n; i++){  // 先背包
            for(int j = 1; j * j <= i; j++){  // 再物品
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

139. 單詞拆分

leetcode題目鏈接：139. 單詞拆分

給你一個(gè)字符串 s 和一個(gè)字符串列表 wordDict 作為字典，判定 s 是否可以由空格拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。

說(shuō)明：拆分時(shí)可以重復(fù)使用字典中的單詞。

示例一：

輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因?yàn)?"leetcode" 可以被拆分成 "leet code"。

示例二：

輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因?yàn)?"applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重復(fù)使用字典中的單詞。

示例三：

輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false

單詞就是物品，字符串s就是背包，單詞能否組成字符串s，就是問(wèn)物品能不能把背包裝滿。

拆分時(shí)可以重復(fù)使用字典中的單詞，說(shuō)明就是一個(gè)完全背包！

1.確定dp數(shù)組以及下標(biāo)的含義

dp[i] : 字符串長(zhǎng)度為i的話，dp[i]為true，表示可以拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。

2.確定遞推公式

如果確定dp[j] 是true，且 [j, i] 這個(gè)區(qū)間的子串出現(xiàn)在字典里，那么dp[i]一定是true。（j < i ）。

所以遞推公式是 if([j, i] 這個(gè)區(qū)間的子串出現(xiàn)在字典里 && dp[j]是true) 那么 dp[i] = true。

3.dp數(shù)組如何初始化

從遞歸公式中可以看出，dp[i] 的狀態(tài)依靠 dp[j]是否為true，那么dp[0]就是遞歸的根基，dp[0]一定要為true，否則遞歸下去后面都都是false了。

下標(biāo)非0的dp[i]初始化為false，只要沒(méi)有被覆蓋說(shuō)明都是不可拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。

4.確定遍歷順序

本題最終要求的是是否都出現(xiàn)過(guò)，所以對(duì)出現(xiàn)單詞集合里的元素是組合還是排列，并不在意！

所以本題的兩個(gè)for循環(huán)的關(guān)系是：外層for循環(huán)遍歷物品，內(nèi)層for遍歷背包或者外層for遍歷背包，內(nèi)層for循環(huán)遍歷物品都是可以的！

5.舉例推導(dǎo)dp數(shù)組

省略。

Java代碼實(shí)現(xiàn)：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 動(dòng)態(tài)規(guī)劃
        // dp[i] 表示以i-1結(jié)尾的字符串能否拆分成字典中得單詞
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i = 1; i <= s.length(); i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && wordDict.contains(s.substring(j, i))){
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

簡(jiǎn)單的優(yōu)化，當(dāng)dp[i]=true，可以break，減少遍歷的次數(shù)。

for(int i = 1; i <= s.length(); i++){
    for(int j = 0; j < i; j++){
        if(dp[j] && wordDict.contains(s.substring(j, i))){
            dp[i] = true;
            break;
        }
    }
}

四、完全背包問(wèn)題總結(jié)

1. 動(dòng)規(guī)五步分析法

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義
2. 確定遞推公式
3. dp數(shù)組如何初始化
4. 確定遍歷順序
5. 舉例推導(dǎo)dp數(shù)組

2. 背包遞推公式

問(wèn)裝滿背包有幾種方法：dp[i] += dp[i - nums[j]] ，對(duì)應(yīng)題目如下：

518. 零錢兌換 II

377. 組合總和 Ⅳ

問(wèn)裝滿背包所有物品的最小個(gè)數(shù)：dp[i] = min(dp[i - coins[j]] + 1, dp[i]); ，對(duì)應(yīng)題目如下：

322. 零錢兌換

279.完全平方數(shù)

3. 遍歷順序

純完全背包的一維dp數(shù)組實(shí)現(xiàn)，先遍歷物品還是先遍歷背包都是可以的，且第二層for循環(huán)是從小到大遍歷。

如果求組合數(shù)就是外層for循環(huán)遍歷物品，內(nèi)層for遍歷背包。

求組合數(shù)：518. 零錢兌換 II

如果求排列數(shù)就是外層for遍歷背包，內(nèi)層for循環(huán)遍歷物品。

求排列數(shù)：377. 組合總和 Ⅳ

如果求最小數(shù)，那么兩層for循環(huán)的先后順序就無(wú)所謂了。

求最小數(shù)：322. 零錢兌換、279.完全平方數(shù)

對(duì)于背包問(wèn)題，其實(shí)遞推公式算是容易的，難是難在遍歷順序上。

參考：完全背包理論基礎(chǔ)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-435693.html

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃之背包問(wèn)題——完全背包的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！