0-1背包

有N件物品和?個(gè)最多能被重量為W 的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i] 。每件物品只能??次，求解將哪些物品裝?背包?物品價(jià)值總和最?。

image.png

每?件物品其實(shí)只有兩個(gè)狀態(tài)，取或者不取，所以可以使?回溯法搜索出所有的情況，那么時(shí)間復(fù)雜度就是O(2^n)，這?的n表示物品數(shù)量。
所以暴?的解法是指數(shù)級(jí)別的時(shí)間復(fù)雜度。進(jìn)?才需要?jiǎng)討B(tài)規(guī)劃的解法來(lái)進(jìn)?優(yōu)化！

示例

背包最?重量為4。
物品為

image.png

問(wèn)背包能背的物品最?價(jià)值是多少？

解法一:?維dp數(shù)組01背包

使用動(dòng)態(tài)規(guī)劃五部曲分析?波。
1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

對(duì)于背包問(wèn)題，有?種寫(xiě)法， 是使??維數(shù)組，即dp[i][j] 表示從下標(biāo)為[0-i]的物品?任意取，放進(jìn)容量為j的背包，價(jià)值總和最?是多少,如下圖

image.png

2. 確定遞推公式

再回顧?下dp[i][j]的含義：從下標(biāo)為[0-i]的物品?任意取，放進(jìn)容量為j的背包，價(jià)值總和最?是多少。
那么可以有兩個(gè)?向推出來(lái)dp[i][j]，

• 不選擇第i件物品,背包容量為j，??不放物品i的最?價(jià)值，此時(shí)dp[i][j]就是dp[i - 1][j]
• 選擇第i件物品,那么dp[i - 1][j - weight[i]] + value[i] （物品i的價(jià)值），就是背包放物品i得到的最?價(jià)值
  所以遞歸公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp數(shù)組如何初始化
   關(guān)于初始化，?定要和dp數(shù)組的定義吻合，否則到遞推公式的時(shí)候就會(huì)越來(lái)越亂。

?先從dp[i][j]的定義觸發(fā)，如果背包容量j為0的話，即dp[i][0]，?論是選取哪些物品，背包價(jià)值總和?定為0。如圖：

image.png

在看其他情況。

• 狀態(tài)轉(zhuǎn)移?程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推導(dǎo)出來(lái)，那么i為0的時(shí)候就?定要初始化。
  dp[0][j]，即：i為0，存放編號(hào)0的物品的時(shí)候，各個(gè)容量的背包所能存放的最?價(jià)值。
  代碼如下：

// 倒敘遍歷
for (int j = bagWeight; j >= weight[0]; j--) {
 dp[0][j] = dp[0][j - weight[0]] + value[0]; // 初始化i為0時(shí)候的情況
}

備注:這個(gè)初始化為什么是倒敘的遍歷的？正序遍歷就不?么？
正序遍歷還真就不?，dp[0][j]表示容量為j的背包存放物品0時(shí)候的最?價(jià)值，物品0的價(jià)值就是15，因?yàn)轭}?中說(shuō)了每個(gè)物品只有?個(gè)！所以dp[0][j]如果不是初始值的話，就應(yīng)該都是物品0的價(jià)值，也就是15。
但如果?旦正序遍歷了，那么物品0就會(huì)被重復(fù)加?多次！ 例如代碼如下：

// 正序遍歷
for (int j = weight[0]; j <= bagWeight; j++) {
 dp[0][j] = dp[0][j - weight[0]] + value[0];
}

例如dp[0][1] 是15，到了dp[0][2] = dp[0][2 - 1] + 15; 也就是dp[0][2] = 30 了，那么就是物品0被重復(fù)放?了。

所以?定要倒敘遍歷，保證物品0只被放??次！這?點(diǎn)對(duì)01背包很重要，后?在講解滾動(dòng)數(shù)組的時(shí)
候，還會(huì)?到倒敘遍歷來(lái)保證物品使??次！
此時(shí)dp數(shù)組初始化情況如圖所示：

image.png

這樣才能讓dp數(shù)組在遞歸公式的過(guò)程中取最?的價(jià)值，?不是被初始值覆蓋了。
最后初始化代碼如下：

// 初始化 dp
vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
for (int j = bagWeight; j >= weight[0]; j--) {
 dp[0][j] = dp[0][j - weight[0]] + value[0];
}

4. 確定遍歷順序
   在如下圖中，可以看出，有兩個(gè)遍歷的維度：物品與背包重量

   
   
   image.png

那么問(wèn)題來(lái)了，先遍歷 物品還是先遍歷背包重量呢？
一:我先給出先遍歷物品，然后遍歷背包重量的代碼。

// weight數(shù)組的?? 就是物品個(gè)數(shù)
for(int i = 1; i < weight.size(); i++) { // 遍歷物品
 for(int j = 0; j <= bagWeight; j++) { // 遍歷背包容量
 if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 這個(gè)是為了展現(xiàn)dp數(shù)組?元素的變化
 else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
 }
}

二:先遍歷背包，再遍歷物品

// weight數(shù)組的?? 就是物品個(gè)數(shù)
for(int j = 0; j <= bagWeight; j++) { // 遍歷背包容量
 for(int i = 1; i < weight.size(); i++) { // 遍歷物品
 if (j < weight[i]) dp[i][j] = dp[i - 1][j];
 else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
 }
}

小結(jié):dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 遞歸公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推導(dǎo)出來(lái)的。
dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上??向（包括正左和正上兩個(gè)?向），那么不論是先遍歷物品，再遍歷背包,還是先遍歷背包,再遍歷物品
雖然兩個(gè)for循環(huán)遍歷的次序不同，但是dp[i][j]所需要的數(shù)據(jù)就是左上?，根本不影響
dp[i][j]公式的推導(dǎo)！
但先遍歷物品再遍歷背包這個(gè)順序更好理解。

5. 推導(dǎo)dp數(shù)組
   來(lái)看?下對(duì)應(yīng)的dp數(shù)組的數(shù)值，如圖：

   
   
   image.png
   
   

   最終結(jié)果就是dp[2][4]。

做動(dòng)態(tài)規(guī)劃的題?，最好的過(guò)程就是??在紙上舉?個(gè)例?把對(duì)應(yīng)的dp數(shù)組的數(shù)值推導(dǎo)?下，然后在動(dòng)?寫(xiě)代碼！
如果推導(dǎo)明?了，代碼寫(xiě)出來(lái)就算有問(wèn)題，只要把dp數(shù)組打印出來(lái)，對(duì)??下和??推導(dǎo)的有什么差異，很快就可以發(fā)現(xiàn)問(wèn)題了。

解法二:?維dp數(shù)組（滾動(dòng)數(shù)組）

對(duì)于背包問(wèn)題其實(shí)狀態(tài)都是可以壓縮的。
在使??維數(shù)組的時(shí)候，遞推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其實(shí)可以發(fā)現(xiàn)如果把dp[i - 1]那?層拷?到dp[i]上，表達(dá)式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j- weight[i]] + value[i]);
于其把dp[i - 1]這?層拷?到dp[i]上，不如只??個(gè)?維數(shù)組了，只?dp[j]（?維數(shù)組，也可以理解是?個(gè)滾動(dòng)數(shù)組）。

再來(lái)回顧下
dp[i][j]?的i和j表達(dá)的是什么了，i是物品，j是背包容量。
dp[i][j] 表示從下標(biāo)為[0-i]的物品?任意取，放進(jìn)容量為j的背包，價(jià)值總和最?是多少。

1. 確定dp數(shù)組的定義

在?維dp數(shù)組中，dp[j]表示：容量為j的背包，所背的物品價(jià)值可以最?為dp[j]。

2. ?維dp數(shù)組的遞推公式

dp[j]為 容量為j的背包所背的最?價(jià)值，那么如何推導(dǎo)dp[j]呢？
dp[j]可以通過(guò)dp[j - weight[j]]推導(dǎo)出來(lái)，dp[j - weight[i]]表示容量為j - weight[i]的背包所背的最?價(jià)值。
dp[j - weight[i]] + value[i] 表示 容量為 j - 物品i重量 的背包 加上 物品i的價(jià)值。（也就是容量為j的背包，放?物品i了之后的價(jià)值即：dp[j]）

此時(shí)dp[j]有兩個(gè)選擇，?個(gè)是取??dp[j]，?個(gè)是取dp[j - weight[i]] + value[i]，指定是取最?的，畢竟是求最?價(jià)值，
所以遞歸公式為：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

可以看出相對(duì)于?維dp數(shù)組的寫(xiě)法，就是把dp[i][j]中i的維度去掉了。

3. ?維dp數(shù)組如何初始化
   關(guān)于初始化，?定要和dp數(shù)組的定義吻合，否則到遞推公式的時(shí)候就會(huì)越來(lái)越亂。

dp[j]表示：容量為j的背包，所背的物品價(jià)值可以最?為dp[j]，那么dp[0]就應(yīng)該是0，因?yàn)楸嘲萘繛?,所背的物品的最?價(jià)值就是0。
那么dp數(shù)組除了下標(biāo)0的位置，初始為0，其他下標(biāo)應(yīng)該初始化多少呢？
看?下遞歸公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp數(shù)組在推導(dǎo)的時(shí)候?定是取價(jià)值最?的數(shù)，如果題?給的價(jià)值都是正整數(shù)那么?0下標(biāo)都初始化為0就可以了，如果題?給的價(jià)值有負(fù)數(shù)，那么?0下標(biāo)就要初始化為負(fù)?窮。

4. ?維dp數(shù)組遍歷順序
   代碼如下：

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

那么這里依然有問(wèn)題?
?維dp遍歷的時(shí)候，背包容量是從?到?，??維dp遍歷的時(shí)候，背包是從?到?。
為什么呢？
倒敘遍歷是為了保證物品i只被放??次！
舉?個(gè)例?：物品0的重量weight[0] = 1，價(jià)值value[0] = 15
如果正序遍歷
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此時(shí)dp[2]就已經(jīng)是30了，意味著物品0，被放?了兩次，所以不能正序遍歷

為什么倒敘遍歷，就可以保證物品只放??次呢？
倒敘就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp數(shù)組已經(jīng)都初始化為0）
dp[1] = dp[1 - weight[0]] + value[0] = 15

所以從后往前循環(huán)，每次取得狀態(tài)不會(huì)和之前取得狀態(tài)重合，這樣每種物品就只取?次了。

為什么?維dp數(shù)組歷的時(shí)候不?倒敘呢？
因?yàn)閷?duì)于?維dp，dp[i][j]都是通過(guò)上?層即dp[i - 1][j]計(jì)算?來(lái)，本層的dp[i][j]并不會(huì)被覆蓋！

代碼中是先遍歷物品嵌套遍歷背包容量，那可不可以先遍歷背包容量嵌套遍歷物品呢？
不可以！
因?yàn)?維dp的寫(xiě)法，背包容量?定是要倒序遍歷，如果遍歷背包容量放在上?層，那么每個(gè)dp[j]就只會(huì)放??個(gè)物品(因?yàn)闀?huì)被覆蓋)，即：背包?只放?了?個(gè)物品。

所以?維dp數(shù)組的背包在遍歷順序上和?維其實(shí)是有很?差異的！

5. 推導(dǎo)dp數(shù)組
   ?維dp，分別?物品0，物品1，物品2 來(lái)遍歷背包，最終得到結(jié)果如下：

   
   
   image.png

完全背包

?個(gè)商品如果可以重復(fù)多次放?是完全背包，?只能放??次是01背包

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

區(qū)別

01背包和完全背包唯?不同就是體現(xiàn)在遍歷順序上

01背包的核?代碼
01背包內(nèi)嵌的循環(huán)是從?到?遍歷，為了保證每個(gè)物品僅被添加?次。

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背包dp狀態(tài)圖如下:

image.png

完全背包核心代碼
完全背包的物品是可以添加多次的，所以要從?到?去遍歷

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

完全背包dp狀態(tài)圖如下：

image.png

出題類型

常見(jiàn)的背包問(wèn)題有
1、組合問(wèn)題。2、True、False問(wèn)題。3、最大最小問(wèn)題。

1、組合問(wèn)題： 377. 組合總和 Ⅳ 494. 目標(biāo)和 518. 零錢兌換 II

2、True、False問(wèn)題： 139. 單詞拆分 416. 分割等和子集

3、最大最小問(wèn)題： 474. 一和零 322. 零錢兌換

組合問(wèn)題公式

dp[i] += dp[i-num]

True、False問(wèn)題公式

dp[i] = dp[i] or dp[i-num]

最大最小問(wèn)題公式

dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)

組合問(wèn)題例子
以目標(biāo)和為例
題?鏈接：https://leetcode-cn.com/problems/target-sum/
給定?個(gè)?負(fù)整數(shù)數(shù)組，a1, a2, ..., an, 和?個(gè)?標(biāo)數(shù)，S?，F(xiàn)在你有兩個(gè)符號(hào) + 和 -。對(duì)于數(shù)組中的任意?個(gè)整數(shù)，你都可以從 + 或 -中選擇?個(gè)符號(hào)添加在前?
返回可以使最終數(shù)組和為?標(biāo)數(shù) S 的所有添加符號(hào)的?法數(shù)
示例：
輸?：nums: [1, 1, 1, 1, 1], S: 3
輸出：5
解釋：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
?共有5種?法讓最終?標(biāo)和為3。
提示：

• 數(shù)組?空，且?度不會(huì)超過(guò) 20 。
• 初始的數(shù)組的和不會(huì)超過(guò) 1000 。
• 保證返回的最終結(jié)果能被 32 位整數(shù)存下。

思路

本題要如何使表達(dá)式結(jié)果為target，
既然為target，那么就?定有 left組合 - right組合 = target。
left + right等于sum，?sum是固定的。
公式來(lái)了， left - (sum - left) = target -> left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出來(lái)。
所以此時(shí)問(wèn)題就是在集合nums中找出和為left的組合。
假設(shè)加法的總和為x，那么減法對(duì)應(yīng)的總和就是sum - x。
所以我們要求的是 x - (sum - x) = S
x = (S + sum) / 2

此時(shí)問(wèn)題就轉(zhuǎn)化為，裝滿容量為x背包，有?種?法
?家看到(S + sum) / 2 應(yīng)該擔(dān)?計(jì)算的過(guò)程中向下取整有沒(méi)有影響。
這么擔(dān)?就對(duì)了，例如sum 是5，S是2的話其實(shí)就是?解的，所以：

if ((S + sum) % 2 == 1) return 0; // 此時(shí)沒(méi)有?案

看到這種表達(dá)式，應(yīng)該本能的反應(yīng)，兩個(gè)int相加數(shù)值可能溢出的問(wèn)題，當(dāng)然本題并沒(méi)有溢出。
再回歸到01背包問(wèn)題，為什么是01背包呢？
因?yàn)槊總€(gè)物品（題?中的1）只??次！

這次和之前遇到的背包問(wèn)題不?樣了，之前都是求容量為j的背包，最多能裝多少。
本題則是裝滿有?種?法。其實(shí)這就是?個(gè)組合問(wèn)題了。

動(dòng)規(guī)五部曲分析如下：

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

dp[j] 表示：填滿j（包括j）這么?容積的包，有dp[i]種?法

2. 確定遞推公式

有哪些來(lái)源可以推出dp[j]呢？
不考慮nums[i]的情況下，填滿容量為j - nums[i]的背包，有dp[j - nums[i]]中?法。
那么只要搞到nums[i]的話，湊成dp[j]就有dp[j - nums[i]] 種?法。
舉?個(gè)例?,nums[i] = 2： dp[3]，填滿背包容量為3的話，有dp[3]種?法。
那么只需要搞到?個(gè)2（nums[i]），有dp[3]?法可以湊?容量為3的背包，相應(yīng)的就有多少種?法可以湊?容量為5的背包。
那么需要把 這些?法累加起來(lái)就可以了，dp[i] += dp[j - nums[i]]
所以求組合類問(wèn)題的公式，都是類似這種：
dp[j] += dp[j - nums[i]]

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

從遞歸公式可以看出，在初始化的時(shí)候dp[0] ?定要初始化為1，因?yàn)閐p[0]是在公式中?切遞推結(jié)果的起源，如果dp[0]是0的話，遞歸結(jié)果將都是0。
dp[0] = 1，理論上也很好解釋，裝滿容量為0的背包，有1種?法，就是裝0件物品。
dp[j]其他下標(biāo)對(duì)應(yīng)的數(shù)值應(yīng)該初始化為0，從遞歸公式也可以看出，dp[j]要保證是0的初始值，才能正確的由dp[j - nums[i]]推導(dǎo)出來(lái)。

4..確定遍歷順序
01背包問(wèn)題?維dp的遍歷，nums(物品)放在外循環(huán)，target(背包)在內(nèi)循環(huán)，且內(nèi)循環(huán)倒序。

5. 舉例推導(dǎo)dp數(shù)組
   輸?：nums: [1, 1, 1, 1, 1], S: 3
   bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

dp數(shù)組狀態(tài)變化如下：

image.png

如果僅僅是求個(gè)數(shù)的話，就可以?dp，如果要求的是把所有組合列出來(lái)，
還是要使?回溯法爆搜的

零錢兌換 II
鏈接：https://leetcode-cn.com/problems/coin-change-2/

給定不同?額的硬幣和?個(gè)總?額。寫(xiě)出函數(shù)來(lái)計(jì)算可以湊成總?額的硬幣組合數(shù)。假設(shè)每?種?額的硬幣有?限個(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ù)

思路

這是?道典型的背包問(wèn)題，?看到錢幣數(shù)量不限，就知道這是?個(gè)完全背包。
但本題和純完全背包不?樣，純完全背包是能否湊成總?額，?本題是要求湊成總?額的個(gè)數(shù)！

注意題?描述中是湊成總?額的硬幣組合數(shù)，為什么強(qiáng)調(diào)是組合數(shù)呢？
例如示例?：
5 = 2 + 2 + 1
5 = 2 + 1 + 2
這是?種組合，都是 2 2 1。
如果問(wèn)的是排列數(shù)，那么上?就是兩種排列了
組合不強(qiáng)調(diào)元素之間的順序，排列強(qiáng)調(diào)元素之間的順序
我為什么要介紹這些呢，因?yàn)檫@和下?講解遍歷順序息息相關(guān)!
動(dòng)規(guī)五步曲來(lái)分析如下：

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

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

2. 確定遞推公式

dp[j] （考慮coins[i]的組合總和） 就是所有的dp[j - coins[i]]（不考慮coins[i]）相加。
所以遞推公式：dp[j] += dp[j - coins[i]];

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[j - coins[i]]的時(shí)候才不會(huì)影響真正的dp[j]

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)有順序。
   所以純完全背包是能湊成總結(jié)就?，不?管怎么湊的。
   本題是求湊出來(lái)的?案?jìng)€(gè)數(shù)，且每個(gè)?案?jìng)€(gè)數(shù)是為組合數(shù)。

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

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ù)！

如果把兩個(gè)for交換順序，代碼如下：

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ù)組
   輸?: amount = 5, coins = [1, 2, 5] ，dp狀態(tài)圖如下

   
   
   image.png

最后紅?框dp[amount]為最終結(jié)果。

class Solution {
public:
 int change(int amount, vector<int>& coins) {
 vector<int> dp(amount + 1, 0);
 dp[0] = 1;
 for (int i = 0; i < coins.size(); i++) { // 遍歷物品
 for (int j = coins[i]; j <= amount; j++) { // 遍歷背包
 dp[j] += dp[j - coins[i]];
 }
 }
 return dp[amount];
 }
};

小結(jié)

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