Leetcode刷题笔记——动态规划（背包问题）篇

Leetcode刷题笔记——动态规划（背包问题）篇

一、0-1 背包问题

1. 01背包问题简介

有

n

件物品和一个最多能背重量为

w

的背包。第

i

件物品的重量是

weight[i]

，得到的价值是

value[i]

。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大

**1. 确定

dp

数组（

dp table

）以及下标的含义**

dp[i][j]：

从下标为

[0-i]

的物品里任意取，放进容量为

j

的背包，价值总和最大是多少

2. 确定递推公式

case1:

不放物品 i：由

dp[i - 1][j]

推出，即背包容量为

j

，里面不放物品

i

的最大价值

case2:

放物品i：由

dp[i - 1][j - weight[i]]

推出，

dp[i - 1][j - weight[i]]

为背包容量为

j - weight[i]

的时候不放物品

i

的最大价值，那么

dp[i - 1][j - weight[i]] + value[i] 

（物品i的价值），就是背包放物品i得到的最大价值

**故状态转移方程：

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

**

**3.

dp

数组如何初始化**

dp[0][j]

即：使用各个容量的背包存放编号

0

的物品所能获得的最大价值，即第一行的初始化

dp[i][0]

即：背包容量为

0

的时候，存放各个物品编号所能获得的最大价值，即第一列的初始化

其实从递推公式可以看出

dp[i][j]

是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖，这里统一把dp数组统一初始为0，更方便一些

4. 确定遍历顺序
可以看出，有两个遍历的维度：物品与背包重量

**5. 打印

dp

数组**

python代码解法

classSolution:defBagProblem(self, weight: List[int], value: List[int], bag_capacity:int)->int:"""
        :param weight: 物品重量
        :param value: 物品价值
        :param bag_capacity: 背包容量
        :return: 背包所能装的最大价值
        """
        nums =len(weight)
        dp =[[0]*(bag_capacity +1)for _ inrange(nums)]for i inrange(0, bag_capacity +1):if i >= weight[0]:
                dp[0][i]= value[0]for i inrange(1, nums):for capacity inrange(1, bag_capacity +1):# 不放物品i: dp[i - 1][capacity]:背包容量为 capacity 不放物品i的最大价值# 放物品i: dp[i - 1][capacity - weight[i]] + value[i] 的最大价值if capacity >= weight[i]:# 当背包容量大于等于物品重量的时候通过状态转移方程计算最大价值
                    dp[i][capacity]=max(dp[i -1][capacity],
                                          dp[i -1][capacity - weight[i]]+ value[i])else:
                    dp[i][capacity]= dp[i -1][capacity]print(dp)return dp[nums -1][bag_capacity]if __name__ =='__main__':
    s = Solution()
    weight =[1,3,4]# 物品重量
    weight.sort()
    value =[15,20,30]# 物品价值
    value.sort()
    bag_capacity =4print(s.BagProblem(weight, value, bag_capacity))

0-1背包问题的优化
对于背包问题其实状态都是可以压缩的
**1. 确定

dp

数组（

dp table

）以及下标的含义**
在一维

dp

数组中，

dp[j]

表示：容量为

j

的背包，所背的物品价值可以最大为

dp[j]

2. 确定递推公式

dp[j]

为容量为

j

的背包所背的最大价值，那么如何推导

dp[j]

呢？

---

dp[j]

有两个选择：***

case1

：不放物品

i

，取自己

dp[j]

相当于 二维

dp

数组中的

dp[i-1][j]

case2

：放物品

i

，取

dp[j - weight[i]] + value[i]

，放物品

i

，指定是取最大的，毕竟是求最大价值

**3.

dp

数组如何初始化**

dp[j]

表示：容量为

j

的背包，所背的物品价值可以最大为

dp[j]

，那么

dp[0]

就应该是

0

，因为背包容量为

0

所背的物品的最大价值就是

0

物品

0

的重量

weight[0] = 1

，价值

value[0] = 15

正序遍历

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

此时

dp[2]

就已经是

30

了，意味着物品

0

，被放入了两次

***倒序就是先算

dp[2]

---

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了

**4.一维

dp

数组遍历顺序**
二维

dp

遍历的时候，背包容量是从小到大，而一维

dp

遍历的时候，背包是从大到小，
***倒序遍历是为了保证物品

i

只被放入一次！***，一旦正序遍历了，那么物品0就会被重复加入多次！

weight =[1,3,4]# 物品重量
value =[15,20,30]# 物品价值

bag_capacity =4# 背包容量
dp =[0]*(bag_capacity +1)# 表示容量为j的的背包所能装的最大价值为dp[j]for i inrange(0,len(weight)):# 遍历物品for capacity inrange(bag_capacity, weight[i]-1,-1):# 倒序遍历背包容量
        dp[capacity]=max(dp[capacity], dp[capacity - weight[i]]+ value[i])print(f"倒叙遍历背包容量至物品{i}的重量,在每个背包容量下所能装载的最大价值为:{dp}(每个物品只能装一次)")# 倒叙遍历背包容量至物品 0 的重量,在每个背包容量下所能装载的最大价值为:[0, 15, 15, 15, 15](每个物品只能装一次)# 倒叙遍历背包容量至物品 1 的重量,在每个背包容量下所能装载的最大价值为:[0, 15, 15, 20, 35](每个物品只能装一次)# 倒叙遍历背包容量至物品 2 的重量,在每个背包容量下所能装载的最大价值为:[0, 15, 15, 20, 35](每个物品只能装一次)

**5. 打印

dp

数组**

2. 01背包实战练习

第一题：分割等和子集

Leetcode416：分割等和子集：中等题

（详情点击链接见原题）

给你一个 只包含正整数 的非空数组

nums

。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等

这道题目是要找是否可以将这个数组分割成两个子集使得两个子集的元素和相等，那么只要找到集合里能够出现

sum / 2

的子集总和就算是可以分割

• 背包的体积为sum / 2
• 背包要放入的物品（集合里的元素）集合里的元素代表物品的重量和价值
• 背包如果正好装满说明找到了总和为sum / 2 的子集
• 背包中的每一个元素是不可重复放入的

python代码解法(使用二维数组)

classSolution:defcanPartition(self, nums: List[int])->bool:ifsum(nums)%2==1:returnFalse
        target =sum(nums)//2
        dp =[[Falsefor _ inrange(target +1)]for _ inrange(len(nums))]if nums[0]<= target:
            dp[0][nums[0]]=Truefor i inrange(1,len(nums)):# 遍历物品for j inrange(0, target +1):# 遍历背包容量
                dp[i][j]= dp[i -1][j]if nums[i]== j:
                    dp[i][j]=Truecontinueif nums[i]< j:# 1.不选择 nums[i]:说明在[0, i - 1]这个子区间内已经有一部分元素使得它们的和为 j# 2.选择 nums[i],如果在[0, i - 1]这个子区间内找到一部分元素使得它们的和为 j - nums[i]
                    dp[i][j]= dp[i -1][j]or dp[i -1][j - nums[i]]return dp[len(nums)-1][target]

**1. 确定

dp

数组（

dp table

）以及下标的含义**

dp[i]

表示背包总容量为

i

，放进物品后所背的最大重量为

dp[i]

那么如果背包容量为

target

，

dp[target]

就是装满 背包之后的重量，所以 当

dp[target] == target

的时候，背包就装满了

2.确定递推公式
本题相当于往背包里放入数值

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

**3.

dp

数组如何初始化**

dp[0] = 0

，如果题目给的元素都是正整数那么非

0

下标都初始化为

0

就可以了，如果题目所给的元素有负数，那么非

0

下标应初始化为

-∞

，***这样才能让

dp

数组在递推过程中取得最大的价值，而不是被初始值覆盖了***

# 题目说每个数组中的元素不会超过100,数组的大小不会超过200,总和不会大于20000，背包最大只需要其中一半,所以10001大小就可以了
dp =[0]*10001

4.确定遍历顺序：如果使用一维

dp

数组，物品遍历的

for

循环放在外层，遍历背包的

for

循环放在内层，且内层

for

循环倒序遍历

python代码解法

classSolution:defcanPartition(self, nums: List[int])->bool:ifsum(nums)%2!=0:returnFalse
        nums.sort()
        target =sum(nums)//2# 题目说每个数组中的元素不会超过100,数组的大小不会超过200# 总和不会大于20000，背包最大只需要其中一半,所以10001大小就可以了
        dp =[0]*10001for i inrange(0,len(nums)):# 遍历物品(nums中的元素)# 遍历背包容量, 每一个元素一定是不可重复放入,所以从大到小遍历for j inrange(target, nums[i]-1,-1):
                dp[j]=max(dp[j], dp[j - nums[i]]+ nums[i])# 集合中的元素正好可以装满容量为target的背包if dp[target]== target:returnTruereturnFalse

第二题: 目标和

Leetcode494. 目标和：中等题

（详情点击链接见原题）

给你一个非负整数数组

nums

和一个整数

target

。
向数组中的每个整数前添加

'+'

或

'-'

，然后串联起所有整数，可以构造一个表达式

设加法总和为

add

，减法总和为

minus

**

add - minus = target

**
**

add + minus = total

**

add = (target + total) / 2

，

target

是固定的，

total

是固定的，问题就是在集合

nums

中找出和为

add

的组合

**1. 确定

dp

数组（

dp table

）以及下标的含义**

dp[i][j]

：使用下标为

[0, i]

的

nums[i]

能够凑满容量为

j

的背包，有

dp[i][j]

种方法

python代码解法

classSolution:deffindTargetSumWays(self, nums: List[int], target:int)->int:
        total =sum(nums)ifabs(target)> total:return0if(target + total)%2==1:return0
        target_sum =(target + total)//2# 使用下标为 [0, i] 的 nums[i] 能够凑满容量为 j 的背包一共有 dp[i][j] 种方法
        dp =[[0for _ inrange(target_sum +1)]for _ inrange(len(nums)+1)]

        dp[0][0]=1for i inrange(1,len(nums)+1):# 遍历物品for j inrange(target_sum +1):# 遍历背包容量
                dp[i][j]= dp[i -1][j]# 不选取当前元素if j >= nums[i -1]:
                    dp[i][j]+= dp[i -1][j - nums[i -1]]# 选当前元素return dp[len(nums)][target_sum]if __name__ =='__main__':
    s = Solution()
    nums =[1,1,1,1,1]
    target =3print(s.findTargetSumWays(nums, target))

第三题: 一和零

Leetcode474. 一和零：中等题

（详情点击链接见原题）

给你一个二进制字符串数组

strs

和两个整数

m

和

n

。
请你找出并返回

strs

的最大子集的长度，该子集中 最多 有

m

个

0

和

n

个

1

第四题: 最后一块石头的重量 II

Leetcode1049. 最后一块石头的重量 II：中等题

（详情点击链接见原题）

有一堆石头，用整数数组

stones

表示。其中

stones[i]

表示第

i

块石头的重量。

二、完全背包问题

1.完全背包问题简介

有

N

件物品和一个最多能背重量为

W

的背包。第i件物品的重量是

weight[i]

，得到的价值是

value[i]

。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件

weight =[1,3,4]# 物品重量
value =[15,20,30]# 物品价值

bag_capacity =4# 背包容量
dp =[0]*(bag_capacity +1)# 表示容量为j的的背包所能装的最大价值为dp[j]for i inrange(0,len(weight)):# 遍历物品for capacity inrange(weight[i], bag_capacity +1):# 倒序遍历背包容量
        dp[capacity]=max(dp[capacity], dp[capacity - weight[i]]+ value[i])print(f"遍历物品{i}的重量至背包容量,在每个背包容量下所能装载的最大价值为:{dp}(每个物品可以装无限次)")# 遍历物品 0 的重量至背包容量,在每个背包容量下所能装载的最大价值为:[0, 15, 30, 45, 60](每个物品可以装无限次)# 遍历物品 1 的重量至背包容量,在每个背包容量下所能装载的最大价值为:[0, 15, 30, 45, 60](每个物品可以装无限次)# 遍历物品 2 的重量至背包容量,在每个背包容量下所能装载的最大价值为:[0, 15, 30, 45, 60](每个物品可以装无限次)

重量价值物品0115物品1320物品2430
01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次

2.完全背包实战练习

第一题:零钱兑换

Leetcode322：零钱兑换：中等题

（详情点击链接见原题）

给你一个整数数组

coins

，表示不同面额的硬币；以及一个整数

amount

，表示总金额
计算并返回可以凑成总金额所需的 最少的硬币个数

**1. 确定

dp

数组（

dp table

）以及下标的含义**

dp[j]

：凑足总额为j所需钱币的最少个数为

dp[j]

2.确定递推公式
凑足总额为

j - coins[i]

的最少个数为

dp[j - coins[i]]

，那么只需要加上一个钱币

coins[i]

即

dp[j - coins[i]] + 1

就是

dp[j]

（考虑

coins[i]

）

递推公式：

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

;

**3.

dp

数组如何初始化**

4. 确定遍历顺序

python代码解法

classSolution:defcoinChange(self, coins: List[int], amount:int)->int:
        dp =[float('inf')]*(amount +1)# dp[j]:表示凑成总金额为j的最少硬币个数,初始化为最大值
        dp[0]=0for coin in coins:# 遍历硬币(遍历物品)for j inrange(coin, amount +1):# 遍历金额(遍历背包容量)
                dp[j]=min(dp[j], dp[j - coin]+1)return dp[amount]if dp[amount]!=float('inf')else-1

第二题:单词拆分

Leetcode139：单词拆分：中等题

（详情点击链接见原题）

给你一个字符串

s

和一个字符串列表

wordDict

作为字典。请你判断是否可以利用字典中出现的单词拼接出

s

。

***单词就是物品，字符串

s

就是背包，单词能否组成字符串

s

，就是问物品能不能把背包装满，拆分时可以重复使用字典中的单词说明是一个完全背包***

**1. 确定

dp

数组（

dp table

）以及下标的含义**

dp[i]：

字符串长度为

i

的话，

dp[i]

为

True

表示可以拆分为一个或多个在字典中出现的单词

2.确定递推公式
如果确定

dp[j]

是

True

，且

[j, i]

这个区间的子串出现在字典里，那么

dp[i]

一定是

True

**3.

dp

数组如何初始化**
从递推公式可以看出，

dp[i]

的状态依靠

dp[j]

是否为

True

，那么

dp[0]

初始为

True

完全就是为了递推公式，下标非

0

的

dp[i]

初始化为

False

，只要没有被覆盖说明不可拆分为一个或多个在字典中出现的单词

4. 确定遍历顺序
题目说是拆分为一个或多个在字典中出现的单词，所以这是完全背包，等价于用一个或多个单词(物品)去组成一个字符串(装满一个背包)
单词

"apple", "pen"

是物品，那么我们要求 物品的组合一定是

"apple" + "pen" + "apple"

才能组成

"applepenapple"

，所以这里就强调了物品之间的顺序，所以本题一定是先遍历背包，再遍历物品

python代码解法

classSolution:defwordBreak(self, s:str, wordDict: List[str])->bool:
        wordSet =set(wordDict)
        n =len(s)
        dp =[False]*(n +1)# 表示字符串的前i各字符可以被拆分成单词
        dp[0]=True# 初始状态:表示空字符串可以被拆分为单词for i inrange(1, n +1):# 遍历背包(字符串)for j inrange(i):# 遍历物品(单词)if dp[j]and s[j:i]in wordSet:# 如果s[0:j]可以被拆分为单词并且s[j:i]在单词集合中存在,则s[0:i]可以被拆分为单词
                    dp[i]=Truebreakreturn dp[n]