動態規劃之揹包問題——揹包三講（01揹包，完全揹包，多重揹包）

知乎展示效果不好，最好訪問我的部落格

動態規劃之揹包問題——揹包三講（01揹包，完全揹包，多重揹包）_leoabcd12的部落格-CSDN部落格

復現程式碼隨想錄DP專題動態規劃之揹包問題——揹包三講（01揹包，完全揹包，多重揹包）_leoabcd12的部落格-CSDN部落格復現程式碼隨想錄DP專題

程式碼隨想錄 （programmercarl。com）

動態規劃五部曲

確定dp陣列以及下標的含義

確定遞推公式

dp陣列如何初始化

確定遍歷順序

列印陣列（與自己的推導比較，看哪裡錯了）

01揹包

有N件物品和⼀個最多能被重量為W的揹包。第i件物品的重量是weight［i］，得到的價值是value［i］ 。每件物品只能==用一次==，求解將哪些物品裝⼊揹包裡物品價值總和最大？

1。 例題（二維陣列解法）題目

揹包最大重量為4

重量

價值

物品0

1

15

物品1

3

20

物品2

4

30

問：揹包能背的物品最大價值是多少？

思路

五部曲

陣列含義

使用二維陣列

dp［i］［j］

，含義：從下標為

的物品中任意取，放入容量為

的揹包，價值總和最大為多少

遞推公式由兩個方向推出

一、

不放

物品

的最大價值

揹包容量為

，但不放物品

時的最大價值，即

dp［i-1］［j］

二、

放

物品

的最大價值

先找到

dp［i-1］［j-weight［i］］

，含義：

保證了不放物品

，揹包容量為

其實就是為了給後續放物品

一個預留量，保證放了物品

後背包不會溢位，所以最大價值為

dp［i-1］［j-weight［i］］+value［i］

遞推公式：

陣列初始化

揹包容量

為零時，顯然價值為零

只選物品0，即第一行，顯然只要物品0重量小於等於揹包重量

，價值就為物品0的價值，否則為零

確定遍歷順序

先遍歷揹包還是物品都可以

dp［i］［j］

所需的資料在其左上方

測試用例

image-20220208213840483

程式碼展示

#include

#include

#include

using

namespace

std

；

void

test_2_wei_bag_problem1

（）

{

vector

<

int

>

weight

=

{

1

，

3

，

4

}；

vector

<

int

>

value

=

{

15

，

20

，

30

}；

int

bagWeight

=

4

；

vector

<

vector

<

int

>>

dp

（

weight

。

size

（）

+

1

，

vector

<

int

>

（

bagWeight

+

1

））；

for

（

int

i

=

1

；

i

<

bagWeight

+

1

；

i

++

）

{

if

（

weight

［

0

］

<=

i

）

{

dp

［

0

］［

i

］

=

value

［

0

］；

}

}

for

（

int

j

=

1

；

j

<

bagWeight

+

1

；

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

］）；

}

}

}

cout

<<

dp

［

weight

。

size

（）

-

1

］［

bagWeight

］；

}

int

main

（）

{

test_2_wei_bag_problem1

（）；

return

0

；

}

2。 例題（滾動陣列解法）

還是之前的例子，可以用滾動陣列將陣列降為一維

由遞推公式得：

dp［i］［j］

只和它的上一行有關，且有關元素的行數為

，列數

。那麼我們就可以將陣列壓縮成一維

欲求元素

看這張表，如果陣列是一維的情況，那麼在算出欲求元素後，其實是將欲求元素覆蓋掉

dp［i-1］［j］

，並且我們的遍歷順序也要改變。在二維情況下，我們是按從左到右的順序求的，但在一維中，必須從右向左！因為在求欲求元素時，我們要保證

dp［i-1］［j-weight［i］］

未被覆蓋！同時，必須按照先遍歷物品，再巢狀遍歷揹包的順序。

01揹包內嵌的迴圈是從大到小遍歷，為了保證每個物品僅被新增一次

舉例：

假設物品0重量

，價值

如果是==正序==遍歷

在第一行執行後

的狀態已經發生改變，意味著已經放了物品0，而第二行執行後，疊加了改變後的

，意味著物品0被放了兩次。

那麼為什麼之前在寫二維陣列的時候是正序的？

因為我們實際求的是上一行的狀態，也就是不放當前物品的情況，只不過在滾動陣列中，壓縮了狀態。也即當前元素的公式被執行後，當前元素的狀態（在當前行，包括物品0）覆蓋了先前狀態（在上一行，不含物品0），所以一維中倒序是為了保證物品只被放入一次！

#include

#include

#include

using

namespace

std

；

void

test_1_wei_bag_problem1

（）

{

vector

<

int

>

weight

=

{

1

，

3

，

4

}；

vector

<

int

>

value

=

{

15

，

20

，

30

}；

int

bagWeight

=

4

；

vector

<

int

>

dp

（

bagWeight

+

1

）；

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

］）；

}

}

cout

<<

dp

［

bagWeight

］；

}

int

main

（）

{

test_1_wei_bag_problem1

（）；

return

0

；

}

3。 分割等和子集（LeetCode-416）題目

給你一個

只包含正整數

的

非空

陣列

nums

。請你判斷是否可以將這個陣列分割成兩個子集，使得兩個子集的元素和相等。

示例 1：

輸入：nums = ［1，5，11，5］

輸出：true

解釋：陣列可以分割成 ［1， 5， 5］ 和 ［11］ 。

示例 2：

輸入：nums = ［1，2，3，5］

輸出：false

解釋：陣列不能分割成兩個元素和相等的子集。

提示：

1 <= nums。length <= 200

1 <= nums［i］ <= 100

思路

完全揹包和01揹包區別？

完全揹包中一個商品可以放 ==無數次==

01揹包中一個商品只能放一次

本題如何套？

分割成兩個子集且元素和相等，即揹包容量為

物品重量為

，價值也為

揹包正好裝滿，就說明找到了

五部曲

dp［i］

含義

揹包容量為

時，最大可以湊出的子集和

遞推公式

本題中，物品重量為

，價值也為

陣列初始化

都初始化為零

遍歷順序

先遍歷物品，巢狀遍歷揹包，且揹包遍歷要倒序，不懂的回看例題

測試用例

image-20220210210648061

程式碼展示

class

Solution

{

public

：

bool

canPartition

（

vector

<

int

>

&

nums

）

{

int

sum

=

accumulate

（

nums

。

begin

（），

nums

。

end

（），

0

）；

if

（

sum

%

2

）

{

return

false

；

}

int

target

=

sum

/

2

；

vector

<

int

>

dp

（

target

+

1

）；

for

（

int

i

=

0

；

i

<

nums

。

size

（）；

i

++

）

{

for

（

int

j

=

target

；

j

>=

nums

［

i

］；

j

——

）

{

dp

［

j

］

=

max

（

dp

［

j

］，

dp

［

j

-

nums

［

i

］］

+

nums

［

i

］）；

if

（

dp

［

target

］

==

target

）

{

return

true

；

}

}

}

return

false

；

}

}；

對比卡爾哥的解法，用

target+1

做為陣列大小，優化了空間。遍歷中遇到一個吻合的直接返回

true

，優化了時間。

4。 最後一塊石頭的重量Ⅱ（LeetCode-1049）題目

有一堆石頭，用整數陣列

stones

表示。其中

stones［i］

表示第

i

塊石頭的重量。

每一回合，從中選出

任意兩塊石頭

，然後將它們一起粉碎。假設石頭的重量分別為

x

和

y

，且

x <= y

。那麼粉碎的可能結果如下：

如果

x == y

，那麼兩塊石頭都會被完全粉碎；

如果

x ！= y

，那麼重量為

x

的石頭將會完全粉碎，而重量為

y

的石頭新重量為

y-x

。

最後，

最多隻會剩下一塊

石頭。返回此石頭

最小的可能重量

。如果沒有石頭剩下，就返回

0

。

示例 1：

輸入：stones = ［2，7，4，1，8，1］

輸出：1

解釋：

組合 2 和 4，得到 2，所以陣列轉化為 ［2，7，1，8，1］，

組合 7 和 8，得到 1，所以陣列轉化為 ［2，1，1，1］，

組合 2 和 1，得到 1，所以陣列轉化為 ［1，1，1］，

組合 1 和 1，得到 0，所以陣列轉化為 ［1］，這就是最優值。

示例 2：

輸入：stones = ［31，26，33，21，40］

輸出：5

示例 3：

輸入：stones = ［1，2］

輸出：1

提示：

1 <= stones。length <= 30

1 <= stones［i］ <= 100

思路

如何套？

目的是求

最小的可能重量

，其實也就是湊重量儘可能相等的兩堆。舉個例子

10，1，2，2，2，2，2

。我們就可以分為重量為

和

的兩堆。

五部曲

dp［j］

含義

重量為

的揹包最大可以裝的石頭重量和

遞推公式

本題中，物品重量為

，價值也為

陣列初始化

設預設值零即可

遍歷順序

先遍歷物品，巢狀遍歷揹包，且揹包遍歷要倒序

測試用例

image-20220210220852239

程式碼展示

class

Solution

{

public

：

int

lastStoneWeightII

（

vector

<

int

>

&

stones

）

{

int

sum

=

accumulate

（

stones

。

begin

（），

stones

。

end

（），

0

）；

int

target

=

sum

/

2

；

vector

<

int

>

dp

（

target

+

1

）；

for

（

int

i

=

0

；

i

<

stones

。

size

（）；

i

++

）

{

for

（

int

j

=

target

；

j

>=

stones

［

i

］；

j

——

）

{

dp

［

j

］

=

max

（

dp

［

j

］，

dp

［

j

-

stones

［

i

］］

+

stones

［

i

］）；

}

}

return

sum

-

dp

［

target

］

-

dp

［

target

］；

}

}；

開始時沒有考慮到問題是最小的可能重量。在

stones = ［31，26，33，21，40］

這個樣例中：一堆為

31，26，21

重量和為

，另一堆為

33，40

重量和為

。按照程式碼求法，

target=75

。求的是

dp［75］

。為什麼不是求

dp［73］

？回看陣列定義：重量為

的揹包最大可以裝的石頭重量和。可以看出：其實

dp［75］

與

dp［73］

是相等的

5。 目標和（LeetCode-494）題目

給你一個整數陣列

nums

和一個整數

target

。

向陣列中的每個整數前新增

‘+’

或

‘-’

，然後串聯起所有整數，可以構造一個

表示式

：

例如，

nums = ［2， 1］

，可以在

2

之前新增

‘+’

，在

1

之前新增

‘-’

，然後串聯起來得到表示式

“+2-1”

。

返回可以透過上述方法構造的、運算結果等於

target

的不同

表示式

的數目。

示例 1：

輸入：nums = ［1，1，1，1，1］， target = 3

輸出：5

解釋：一共有 5 種方法讓最終目標和為 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

+1 + 1 + 1 + 1 - 1 = 3

示例 2：

輸入：nums = ［1］， target = 1

輸出：1

提示：

1 <= nums。length <= 20

0 <= nums［i］ <= 1000

0 <= sum（nums［i］） <= 1000

-1000 <= target <= 1000

思路

怎麼套？

分成兩堆，

又因為

所以

這和以前遇到的題目 ==不一樣==

先前：容量為

i

的揹包，最多能裝多少？

這次：填滿容量為

i

的揹包，有多少種方法？

五部曲

陣列定義

dp［j］

表示：填滿容量為

j

的揹包，有

dp［j］

種方法

遞推公式

分兩種情況，一種是不包含當前物品的方法數量，另一種是包含當前物品的方法數量。我們要求的就是二者 ==之和==。為了方便，直接使用一維陣列展示：

陣列初始化

如果是二維陣列，也就是要初始化第一行，即只有物品零的情況，可以想見，填滿揹包容量為零的方法有一種，就是不裝東西。但填滿不為零的揹包的方法卻為零，除非物品重量等於揹包容量。所以在一維陣列中初始化應該是

dp［0］=1 其他為0

遍歷順序

先遍歷物品，巢狀遍歷揹包，且揹包遍歷要倒序

測試用例

image-20220214214054984

程式碼展示

class

Solution

{

public

：

int

findTargetSumWays

（

vector

<

int

>

&

nums

，

int

target

）

{

int

sum

=

accumulate

（

nums

。

begin

（），

nums

。

end

（），

0

）；

if

（（

sum

<

target

）

||

（（

sum

+

target

）

%

2

）

||

（（

sum

+

target

）

<

0

））

{

return

0

；

}

int

left

=

（

sum

+

target

）

/

2

；

vector

<

int

>

dp

（

left

+

1

）；

dp

［

0

］

=

1

；

for

（

int

i

=

0

；

i

<

nums

。

size

（）；

i

++

）

{

for

（

int

j

=

left

；

j

>=

nums

［

i

］；

j

——

）

{

dp

［

j

］

+=

dp

［

j

-

nums

［

i

］］；

}

}

return

dp

［

left

］；

}

}；

6。 一和零（LeetCode-474）題目

給你一個二進位制字串陣列

strs

和兩個整數

m

和

n

。

請你找出並返回

strs

的最大子集的長度，該子集中

最多

有

m

個

0

和

n

個

1

。

如果

x

的所有元素也是

y

的元素，集合

x

是集合

y

的

子集

。

示例 1：

輸入：strs = ［“10”， “0001”， “111001”， “1”， “0”］， m = 5， n = 3

輸出：4

解釋：最多有 5 個 0 和 3 個 1 的最大子集是 {“10”，“0001”，“1”，“0”} ，因此答案是 4 。

其他滿足題意但較小的子集包括 {“0001”，“1”} 和 {“10”，“1”，“0”} 。{“111001”} 不滿足題意，因為它含 4 個 1 ，大於 n 的值 3 。

示例 2：

輸入：strs = ［“10”， “0”， “1”］， m = 1， n = 1

輸出：2

解釋：最大的子集是 {“0”， “1”} ，所以答案是 2 。

提示：

1 <= strs。length <= 600

1 <= strs［i］。length <= 100

strs［i］

僅由

‘0’

和

‘1’

組成

1 <= m， n <= 100

思路

五部曲

dp［i］［j］

含義

最多能裝

i

個

和

j

個

的揹包的==最大子集的數量==

遞推公式

雖然是二維的，但其實只包含揹包重量這一個方面，本質還是滾動陣列。

其中，

和

分別表示當前物品，即當前子集的零和一個數。相當於物品的重量。而後面的加一相當於物品的價值。為什麼是一？因為加上當前物品後，最大子集數量就加一了。

陣列初始化

物品價值不為負數，所以初始化為零即可

遍歷順序

先遍歷物品，巢狀遍歷揹包，且揹包遍歷要倒序

測試用例

本圖為最後狀態

image-20220215203854039

程式碼展示

class

Solution

{

public

：

int

findMaxForm

（

vector

<

string

>

&

strs

，

int

m

，

int

n

）

{

vector

<

vector

<

int

>>

dp

（

m

+

1

，

vector

<

int

>

（

n

+

1

））；

for

（

int

idx

=

0

；

idx

<

strs

。

size

（）；

idx

++

）

{

int

numZero

=

0

，

numOne

=

0

；

for

（

char

val

：

strs

［

idx

］）

{

if

（

val

==

‘0’

）

{

numZero

++

；

}

else

{

numOne

++

；

}

}

for

（

int

i

=

m

；

i

>=

numZero

；

i

——

）

{

for

（

int

j

=

n

；

j

>=

numOne

；

j

——

）

{

dp

［

i

］［

j

］

=

max

（

dp

［

i

］［

j

］，

dp

［

i

-

numZero

］［

j

-

numOne

］

+

1

）；

}

}

}

return

dp

［

m

］［

n

］；

}

}；

完全揹包

1。 例題題目

有N件物品和一個最多能背重量為

的揹包。第

件物品的重量是

，得到的價值是

。每件物品都有無限個（也就是==可以放入揹包多次==），求解將哪些物品裝入揹包裡物品價值總和最大。

完全揹包和01揹包問題唯一不同的地方就是，每種物品有無限件。同樣leetcode上沒有純完全揹包問題，都是需要完全揹包的各種應用，需要轉化成完全揹包問題，所以我這裡還是以純完全揹包問題進行講解理論和原理。

在下面的講解中，我依然舉這個例子：

揹包最大重量為4。

物品為：

重量

價值

物品0

1

15

物品1

3

20

物品2

4

30

==每件商品都有無限個==

問：揹包能背的物品最大價值是多少？

思路

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揹包內嵌的迴圈是從大到小遍歷，為了保證每個物品僅被新增一次

舉例：

假設物品0重量

，價值

如果是==正序==遍歷

在第一行執行後

的狀態已經發生改變，意味著已經放了物品0，而第二行執行後，疊加了改變後的

，意味著物品0被放了兩次。

那麼為什麼之前在寫二維陣列的時候是正序的？

因為我們實際求的是上一行的狀態，也就是不放當前物品的情況，只不過在滾動陣列中，壓縮了狀態。也即當前元素的公式被執行後，當前元素的狀態（在當前行，包括物品0）覆蓋了先前狀態（在上一行，不含物品0），所以一維中倒序是為了保證物品只被放入一次！

而完全揹包的物品是可以新增多次的，所以要從小到大去遍歷

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

］）；

}

}

遍歷順序是否強制先遍歷物品，再遍歷揹包容量？

在01揹包的一維陣列中必須先遍歷物品，再遍歷揹包容量。

而在完全揹包的一維陣列中，迴圈巢狀順序卻無所謂。

因為

dp［j］

是根據它同行的左邊的元素推出來的，而無論哪種順序，它的左值都是更新過的，可用的。

但先後順序可以顛倒的前提是==純==完全揹包問題！題目變化的可能就不行

程式碼展示

#include

#include

#include

using

namespace

std

；

void

test_CompletePack

（）

{

vector

<

int

>

weight

=

{

1

，

3

，

4

}；

vector

<

int

>

value

=

{

15

，

20

，

30

}；

int

bagWeight

=

4

；

vector

<

int

>

dp

（

bagWeight

+

1

）；

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

］）；

}

}

cout

<<

dp

［

bagWeight

］；

}

int

main

（）

{

test_CompletePack

（）；

return

0

；

}

2。 零錢兌換Ⅱ（LeetCode-518）題目

給你一個整數陣列

coins

表示不同面額的硬幣，另給一個整數

amount

表示總金額。

請你計算並返回可以湊成總金額的硬幣組合數。如果任何硬幣組合都無法湊出總金額，返回

0

。

假設每一種面額的硬幣有無限個。

題目資料保證結果符合 32 位帶符號整數。

示例 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

提示：

1 <= coins。length <= 300

1 <= coins［i］ <= 5000

coins

中的所有值

互不相同

0 <= amount <= 5000

思路

本題要點：

硬幣有無限個，所以完全揹包問題

本題要求湊成總金額的

個數

五部曲

dp［j］

含義

湊成總金額為

的硬幣組合數（揹包的容量為

的揹包恰好裝滿的方法數）

遞推公式

陣列初始化

dp［0］=1

從陣列含義看：湊成總金額為零的硬幣組合數為一

遍歷順序

先遍歷物品，巢狀遍歷揹包，且揹包遍歷要正序

本題不是純完全揹包問題，不能交換順序。因為本題求的是組合數，要求元素之間沒有順序。

測試用例

image-20220217135259732

程式碼展示

class

Solution

{

public

：

int

change

（

int

amount

，

vector

<

int

>

&

coins

）

{

vector

<

int

>

dp

（

amount

+

1

）；

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

］；

}

}；

3。 組合總和Ⅳ（LeetCode-377）題目

給你一個由

不同

整陣列成的陣列

nums

，和一個目標整數

target

。請你從

nums

中找出並返回總和為

target

的元素組合的個數。

題目資料保證答案符合 32 位整數範圍。

示例 1：

輸入：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）

請注意，順序不同的序列被視作不同的組合。

示例 2：

輸入：nums = ［9］， target = 3

輸出：0

提示：

1 <= nums。length <= 200

1 <= nums［i］ <= 1000

nums

中的所有元素

互不相同

1 <= target <= 1000

**進階：**如果給定的陣列中含有負數會發生什麼？問題會產生何種變化？如果允許負數出現，需要向題目中新增哪些限制條件？

思路

由示例一最後一行得，題目看似求的組合數，實際上求的是排序數

五部曲

dp［j］

含義

湊成目標正整數為

的排列個數（使揹包容量為

的揹包恰好裝滿的組合數——不同排序算做不同組合）

遞推公式

陣列初始化

dp［0］=1

遍歷順序

先遍歷揹包，巢狀遍歷物品，且物品遍歷要正序

如果把遍歷 nums（物品）放在外迴圈，遍歷target的作為內迴圈的話，舉⼀個例子：計算dp［4］的時候，結果集只有

{1，3}

這樣的集合，不會有

{3，1}

這樣的集合，因為nums遍歷放在外層，3只能出現在1後面

程式碼展示

class

Solution

{

public

：

int

combinationSum4

（

vector

<

int

>

&

nums

，

int

target

）

{

vector

<

int

>

dp

（

target

+

1

）；

dp

［

0

］

=

1

；

for

（

int

j

=

0

；

j

<=

target

；

j

++

）

{

for

（

int

i

=

0

；

i

<

nums

。

size

（）；

i

++

）

{

if

（

j

>=

nums

［

i

］

&&

dp

［

j

］

<

INT_MAX

-

dp

［

j

-

nums

［

i

］］）

{

dp

［

j

］

+=

dp

［

j

-

nums

［

i

］］；

}

}

}

return

dp

［

target

］；

}

}；

4。 爬樓梯（改寫成完全揹包）題目

原題為LeetCode-70，是一道簡單動態規劃，現改寫為：

假設你正在爬樓梯。需要 n 階你才能到達樓頂。 每次你可以爬

個臺階。你有多少種不同的方法可以爬到樓頂呢

思路

一步爬一個或兩個或三個或

個就是物品，樓頂就是揹包，其實就是問裝滿揹包的方法有多少種。再想這是排序數還是組合數？明顯先2後1（先爬2階樓梯再爬1階樓梯）和先1後2是不同的方法，所以求的是排序數，那麼就要求先遍歷揹包，巢狀遍歷物品

五部曲

dp［j］

含義

爬到有

個臺階的樓頂的方法數

遞推公式

陣列初始化

dp［0］=1

遍歷順序

上文已說明

程式碼實現

class

Solution

{

public

：

int

climbStairs

（

int

n

，

int

m

）

{

vector

<

int

>

dp

（

n

+

1

，

0

）；

dp

［

0

］

=

1

；

for

（

int

i

=

1

；

i

<=

n

；

i

++

）

{

// 遍歷揹包

for

（

int

j

=

1

；

j

<=

m

；

j

++

）

{

// 遍歷物品

if

（

i

-

j

>=

0

）

dp

［

i

］

+=

dp

［

i

-

j

］；

}

}

return

dp

［

n

］；

}

}；

程式碼中m表示最多可以爬m個臺階，程式碼中把m改成2就是本題70。爬樓梯可以AC的程式碼了

5。 零錢兌換（LeetCode-322）題目

給你一個整數陣列

coins

，表示不同面額的硬幣；以及一個整數

amount

，表示總金額。

計算並返回可以湊成總金額所需的

最少的硬幣個數

。如果沒有任何一種硬幣組合能組成總金額，返回

-1

。

你可以認為每種硬幣的數量是無限的。

示例 1：

輸入：coins = ［1， 2， 5］， amount = 11

輸出：3

解釋：11 = 5 + 5 + 1

示例 2：

輸入：coins = ［2］， amount = 3

輸出：-1

示例 3：

輸入：coins = ［1］， amount = 0

輸出：0

提示：

1 <= coins。length <= 12

1 <= coins［i］ <= 231 - 1

0 <= amount <= 104

思路

五部曲

dp［j］

含義

湊成總金額為

所需的最少硬幣數

遞推公式

求最少硬幣數，一種就是不含當前物品（這裡說的當前物品就是指當前的這枚硬幣，假如當前硬幣值為2，不是說揹包裡就不含硬幣值為2的硬幣了，因為是硬幣無限枚，所以很可能有，而是說不含當前這枚硬幣值為2的硬幣）的硬幣數，數值保持不變。另一種是含當前物品的硬幣數，數值要加一（加上當前物品）

陣列初始化

湊成總金額為2的硬幣數肯定為零，而其他要初始化為最大值，不然在執行遞推公式時初始值會覆蓋

遍歷順序

這裡求最少硬幣數量，硬幣是組合數還是排列數都無所謂，所以順序隨意

程式碼實現

class

Solution

{

public

：

int

coinChange

（

vector

<

int

>

&

coins

，

int

amount

）

{

vector

<

int

>

dp

（

amount

+

1

，

INT_MAX

）；

dp

［

0

］

=

0

；

for

（

int

i

=

0

；

i

<

coins

。

size

（）；

i

++

）

{

for

（

int

j

=

coins

［

i

］；

j

<=

amount

；

j

++

）

{

// 如果dp［j - coins［i］］是初始值則跳過

if

（

dp

［

j

-

coins

［

i

］］

！=

INT_MAX

）

{

dp

［

j

］

=

min

（

dp

［

j

］，

dp

［

j

-

coins

［

i

］］

+

1

）；

}

}

}

return

dp

［

amount

］

==

INT_MAX

？

-

1

：

dp

［

amount

］；

}

}；

易錯點在

是初始值沒有跳過，還有記得沒有任何一種硬幣組合能組成總金額，返回

-1

6。 完全平方數（LeetCode-279）題目

給你一個整數

n

，返回

和為

n

的完全平方數的最少數量

。

完全平方數

是一個整數，其值等於另一個整數的平方；換句話說，其值等於一個整數自乘的積。例如，

1

、

4

、

9

和

16

都是完全平方數，而

3

和

11

不是。

示例 1：

輸入：n = 12

輸出：3

解釋：12 = 4 + 4 + 4

示例 2：

輸入：n = 13

輸出：2

解釋：13 = 4 + 9

提示：

1 <= n <= 104

思路

看到示例一的

知道是完全揹包問題，本題求和為

n

的完全平方數的

最少數量

五部曲

dp［j］

含義

和為

的完全平方數的最少數量

遞推公式

想一下，如果訪問的當前物品是完全平方數，那麼就分別求裝它和不裝它的數量，二者取小值。如果不是完全平方數，那麼還是取不裝它的數量

陣列初始化

和為

的完全平方數的最少數量肯定為零，而其他要初始化為最大值

遍歷順序

這裡求最少數量，是組合數還是排列數都無所謂，所以順序隨意

程式碼展示

image-20220219203930991

class

Solution

{

public

：

int

numSquares

（

int

n

）

{

vector

<

int

>

dp

（

n

+

1

，

INT_MAX

）；

dp

［

0

］

=

0

；

for

（

int

i

=

1

；

i

<=

n

；

i

++

）

{

bool

flag

=

false

；

if

（

i

==

1

）

{

flag

=

true

；

}

for

（

int

k

=

0

；

k

<

i

；

k

++

）

{

if

（

k

*

k

==

i

）

{

flag

=

true

；

break

；

}

}

for

（

int

j

=

i

；

j

<=

n

；

j

++

）

{

if

（

flag

&&

dp

［

j

-

i

］

！=

INT_MAX

）

{

dp

［

j

］

=

min

（

dp

［

j

］，

dp

［

j

-

i

］

+

1

）；

}

}

}

return

dp

［

n

］；

}

}；

分析一下，很快寫出來了。但時間複雜度過於之高。那肯定是求完全平方數沒有處理好。看了下題解，是我的物品選錯了，我是遍歷數然後判斷它是不是完全平方數，但這樣做就煩了。數值

什麼時候完全平方數？說白了

是整數。那我的物品就取

class

Solution

{

public

：

int

numSquares

（

int

n

）

{

vector

<

int

>

dp

（

n

+

1

，

INT_MAX

）；

dp

［

0

］

=

0

；

for

（

int

i

=

1

；

i

*

i

<=

n

；

i

++

）

{

for

（

int

j

=

i

*

i

；

j

<=

n

；

j

++

）

{

dp

［

j

］

=

min

（

dp

［

j

］，

dp

［

j

-

i

*

i

］

+

1

）；

}

}

return

dp

［

n

］；

}

}；

7。 單詞拆分（LeetCode-139）題目

給你一個字串

s

和一個字串列表

wordDict

作為字典。請你判斷是否可以利用字典中出現的單詞拼接出

s

。

**注意：**不要求字典中出現的單詞全部都使用，並且字典中的單詞可以重複使用。

示例 1：

輸入： s = “leetcode”， wordDict = ［“leet”， “code”］

輸出： true

解釋： 返回 true 因為 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2：

輸入： s = “applepenapple”， wordDict = ［“apple”， “pen”］

輸出： true

解釋： 返回 true 因為 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。

注意，你可以重複使用字典中的單詞。

示例 3：

輸入： s = “catsandog”， wordDict = ［“cats”， “dog”， “sand”， “and”， “cat”］

輸出： false

提示：

1 <= s。length <= 300

1 <= wordDict。length <= 1000

1 <= wordDict［i］。length <= 20

s

和

wordDict［i］

僅有小寫英文字母組成

wordDict

中的所有字串

互不相同

思路

不會，卡爾哥的也沒看懂。然後發現官方題解很清晰

我們定義

dp［i］

表示字串

s

前

i

個字元組成的字串

s［0~i−1］

是否能被空格拆分成若干個字典中出現的單詞。從前往後計算考慮轉移方程，每次轉移的時候我們需要列舉包含位置

i-1

的最後一個單詞，看它是否出現在字典中以及除去這部分的字串是否合法即可。公式化來說，我們需要列舉

s［0~i-1］

中的分割點

j

，看

s［0~j-1］

組成的字串

（預設 j = 0 時

為空串）和

s［j~i-1］

組成的字串

是否都合法，如果兩個字串均合法，那麼按照定義

和

拼接成的字串也同樣合法。由於計算到

dp［i］

時我們已經計算出了

dp［0~i−1］

的值，因此字串

是否合法可以直接由

dp［j］

得知，剩下的我們只需要看

是否合法即可，因此我們可以得出如下轉移方程

五部曲

dp［i］

含義

表示字串前

i

個字元組成的字串

s［0~i−1］

是否能被空格拆分成若干個字典中出現的單詞

遞推公式

陣列初始化

dp［0］=true

表示字串為空，但題目中說了“給定⼀個非空字串 s” 所以測試資料中不會出現i為0的情況，那麼dp［0］初始為true完全就是為了推導公式。下標非0的dp［i］初始化為false，只要沒有被覆蓋說明都是不可拆分為⼀個或多個在字典中出現的單詞。

遍歷順序

實在是沒看懂，直接複製卡爾哥的原話了

題⽬中說是拆分為⼀個或多個在字典中出現的單詞，所以這是完全揹包。

還要討論兩層for迴圈的前後循序。

如果求組合數就是外層for迴圈遍歷物品，內層for遍歷揹包。

如果求排列數就是外層for遍歷揹包，內層for迴圈遍歷物品。

本題最終要求的是是否都出現過，所以對出現單詞集合⾥的元素是組合還是排列，並不在意！

那麼本題使⽤求排列的⽅式，還是求組合的⽅式都可以。

即：外層for迴圈遍歷物品，內層for遍歷揹包 或者 外層for遍歷揹包，內層for迴圈遍歷物品 都是可以的。

但本題還有特殊性，因為是要求⼦串，最好是遍歷揹包放在外迴圈，將遍歷物品放在內迴圈。如果要是外層for迴圈遍歷物品，內層for遍歷揹包，就需要把所有的⼦串都預先放在⼀個容器⾥。（如果不理解的話，可以⾃⼰嘗試這麼寫⼀寫就理解了）所以最終我選擇的遍歷順序為：遍歷揹包放在外迴圈，將遍歷物品放在內迴圈。內迴圈從前到後。

測試用例

image-20220219222208744

程式碼展示

class

Solution

{

public

：

bool

wordBreak

（

string

s

，

vector

<

string

>

&

wordDict

）

{

unordered_set

<

string

>

wordset

（

wordDict

。

begin

（），

wordDict

。

end

（））；

vector

<

bool

>

dp

（

s

。

size

（）

+

1

，

false

）；

dp

［

0

］

=

true

；

for

（

int

i

=

0

；

i

<=

s

。

size

（）；

i

++

）

{

for

（

int

j

=

0

；

j

<

i

；

j

++

）

{

if

（

dp

［

j

］

&&

wordset

。

find

（

s

。

substr

（

j

，

i

-

j

））

！=

wordset

。

end

（））

{

dp

［

i

］

=

true

；

break

；

}

}

}

return

dp

［

s

。

size

（）］；

}

}；

多重揹包

LeetCode上無對應題目，只簡單介紹

1。 多重揹包例題題目

有N種物品和一個容量為

的揹包。第i種物品最多有

件可用，每件耗費的空間是

，價值是

。求解將哪些物品裝入揹包可使這些物品的耗費的空間 總和不超過揹包容量，且價值總和最大。

多重揹包和01揹包是非常像的， 為什麼和01揹包像呢？

每件物品最多有

件可用，把

件攤開，其實就是一個==01揹包==問題了。

例如：

揹包最大重量為10。

物品為：

重量

價值

數量

物品0

1

15

2

物品1

3

20

3

物品2

4

30

2

問揹包能背的物品最大價值是多少？

和如下情況有區別麼？

重量

價值

數量

物品0

1

15

1

物品0

1

15

1

物品1

3

20

1

物品1

3

20

1

物品1

3

20

1

物品2

4

30

1

物品2

4

30

1

毫無區別，這就轉成了一個01揹包問題了，且每個物品只用一次。

思路

將有多件的物品展開，就可將完全揹包轉換成01揹包

程式碼展示

#include

#include

using

namespace

std

；

void

test_multi_pack

（）

{

vector

<

int

>

weight

=

{

1

，

3

，

4

}；

vector

<

int

>

value

=

{

15

，

20

，

30

}；

vector

<

int

>

nums

=

{

2

，

3

，

2

}；

int

bagWeight

=

10

；

for

（

int

i

=

0

；

i

<

nums

。

size

（）；

i

++

）

{

while

（

nums

［

i

］

>

1

）

{

// nums［i］保留到1，把其他物品都展開

weight

。

push_back

（

weight

［

i

］）；

value

。

push_back

（

value

［

i

］）；

nums

［

i

］

——

；

}

}

vector

<

int

>

dp

（

bagWeight

+

1

，

0

）；

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

］）；

}

for

（

int

j

=

0

；

j

<=

bagWeight

；

j

++

）

{

cout

<<

dp

［

j

］

<<

“ ”

；

}

cout

<<

endl

；

}

cout

<<

dp

［

bagWeight

］

<<

endl

；

}

int

main

（）

{

test_multi_pack

（）；

return

0

；

}

小結

做了這些題目後，感覺在沒有系統學習dp之前，抓不住重點，有時稀裡糊塗ac了，但不能完整推出來。所以說，卡爾哥的專題真的很有幫助！

本文使用 Zhihu On VSCode 創作併發布