Leetcode刷题笔记——动态规划（背包问题）篇_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代码解法

class Solution:
    def BagProblem(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 _ in range(nums)]
        for i in range(0, bag_capacity + 1):
            if i >= weight[0]:
                dp[0][i] = value[0]
        for i in range(1, nums):
            for capacity in range(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 = 4
    print(s.BagProblem(weight, value, bag_capacity))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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 in range(0, len(weight)):     # 遍历物品
    for capacity in range(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](每个物品只能装一次)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5. 打印 dp 数组

2. 01背包实战练习

第一题：分割等和子集

Leetcode416：分割等和子集：中等题 （详情点击链接见原题）

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等

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

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

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

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        
        if sum(nums) % 2 == 1:
            return False
        target = sum(nums) // 2
        dp = [[False for _ in range(target + 1)] for _ in range(len(nums))]

        if nums[0] <= target:
            dp[0][nums[0]] = True
        for i in range(1, len(nums)):  # 遍历物品
            for j in range(0, target + 1):  # 遍历背包容量
                dp[i][j] = dp[i - 1][j]

                if nums[i] == j:
                    dp[i][j] = True
                    continue
                if 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
1
2

4.确定遍历顺序：如果使用一维 dp 数组，物品遍历的 for 循环放在外层，遍历背包的 for 循环放在内层，且内层 for 循环倒序遍历

python代码解法

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

        # 集合中的元素正好可以装满容量为target的背包
        if dp[target] == target:
            return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第二题: 目标和

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代码解法

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if abs(target) > total:
            return 0
        if (target + total) % 2 == 1:
            return 0
        target_sum = (target + total) // 2

        # 使用下标为 [0, i] 的 nums[i] 能够凑满容量为 j 的背包一共有 dp[i][j] 种方法
        dp = [[0 for _ in range(target_sum + 1)] for _ in range(len(nums) + 1)]

        dp[0][0] = 1

        for i in range(1, len(nums) + 1):  # 遍历物品
            for j in range(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 = 3
    print(s.findTargetSumWays(nums, target))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

第三题: 一和零

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 in range(0, len(weight)):     # 遍历物品
    for capacity in range(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](每个物品可以装无限次)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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代码解法

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

第二题: 完全平方数

Leetcode279. 完全平方数：中等题 （详情点击链接见原题）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是

解题思路
完全平方数就是物品（可以无限使用），凑成正整数 n 就是背包，问凑满这个背包最少有多少物品
1. 确定 dp 数组（dp table）以及下标的含义
dp[j]: 和为 j 的完全平方数的最少数量为 dp[j]

2.确定递推公式
dp[j] 可由 dp[j - i * i] 推出，dp[j - i * i + 1] 便可以凑成 dp[j]
此时我们要选择最小的 dp[j]，所以递推公式为：dp[j] = min(dp[j - i * i] + 1, dp[j])

3. dp 数组如何初始化
dp[0] 表示和为 0 的完全平方数的最小数量，dp[0] = 0
从递推公式中可以看出，每次 dp[j] 都要选最小的，所以非 0 下标的 dp[j] 一定要初始化为最大值，这样 dp[j] 在递推的时候才不会被初始值覆盖

4. 确定遍历顺序
因为是求最小数，所以遍历顺序没有硬性要求

python代码解法

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [sys.maxsize] * (n + 1)
        dp[0] = 0
        for i in range(n + 1):   # 遍历背包
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i - j * j] + 1, dp[i])
                j += 1
        return dp[n]
1
2
3
4
5
6
7
8
9
10

第二题:零钱兑换II

Leetcode518. 零钱兑换 II：中等题 （详情点击链接见原题）

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0

如果我们把每次可走步数/零钱面额限制为 [1, 2]，把楼梯高度/总金额限制为 3，那么这两道题目就可以抽象成给定 [1,2]，求组成成 3 的组合数和排列数

在爬楼梯问题中，每次可以爬 1 或 2 个台阶，你有多少种不同的方法可以爬到楼顶呢 ?
problem(i) = sub(i - 1) + sub(i - 2) ，dp[i] = dp[i -1] + dp[i - 2]，由于每次我们只关注 dp[i - 1] 和 dp[i - 2]，所以代码种能把数组替换成 2 个变量，降低空间复杂度，可以认为是将 一维数组降维成点，如果我们把问题泛化，不再是固定的 1， 2, 而是任意给定台阶数，例如1，2，5呢？
我们只需要修改我们的 dp 方程 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 5]，也就是 dp[i] = dp[i - 1] + dp[i - j] j = 1, 2, 5
我们再来看零钱兑换，给定不同面额的硬币和一个总金额，求凑成总金额的硬币组合数
problem(i) = sum(problem(i - j)) j = 1 ,2, 5 含义为从成总金额 i 的硬币组合数等于凑成总金额为 i - 1, i - 2, i - 5 的子问题之和

python代码解法(二维DP)

"""
dp[i][j]: 前 i 个硬币凑齐金额 j 的组合数
第一个维度 i 用来记录当前组合有没有用到硬币 coins[i]
第二个维度 j 记录现在凑的金额是多少?
if 金额数 > 硬币数:
    dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j]
else:
    dp[i][j] = dp[i - 1][i]
"""
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [[0 for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
        for k in range(len(coins) + 1):
            dp[k][0] = 1

        for i in range(1, len(coins) + 1):   # 遍历硬币
            for j in range(1, amount + 1):   # 遍历金额
                if j >= coins[i - 1]:
                    dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[len(coins)][amount]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

现在我们来看一下一维数组的解法
我们定义的子问题是必须选择第 k 个硬币时，凑成金额 i 的方案，如果交换了，我们的子问题就变成对于金额 i，我们选择硬币的方案

纯完全背包求的是凑成背包的最大价值是多少，而本题求得是凑成总金额的物品组合个数

1. 确定 dp 数组（dp table）以及下标的含义
dp[j]: 凑成总金额为 j 的货币组合数为 dp[j]

2.确定递推公式
dp[j] 就是所有的 dp[j - coins[i]] 相加，所以递推公式为 dp[j] += dp[j - coins[i]]

3. dp 数组如何初始化
dp[0] = 1：凑成总金额为 0 的货币组合数为1

4. 确定遍历顺序
如果是求装满背包的最大价值和凑成总和的元素的顺序没有关系
本题要求凑成总和的组合数，元素之间明确要求没有顺序

讲究顺序，求排列数（列出和下方对比）

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for i in range(1, amount + 1):  # 遍历背包容量
            for j in range(len(coins)):   # 遍历物品
                coin = coins[j]
                if i < coin:
                    continue
                dp[i] += dp[i - coin]
        return dp[amount]
1
2
3
4
5
6
7
8
9
10
11

求装满背包有多少种方法(求组合数)
python代码解法(一维DP)

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:   # 先遍历物品(硬币)
            for i in range(1, amount + 1):  # 后遍历背包容量(面额)
                if i < coin:
                    continue
                dp[i] += dp[i - coin]
        return dp[amount]
1
2
3
4
5
6
7
8
9
10

第三题:单词拆分

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代码解法

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)    # 表示字符串的前i各字符可以被拆分成单词
        dp[0] = True    # 初始状态:表示空字符串可以被拆分为单词
        for i in range(1, n + 1):   # 遍历背包(字符串)
            for j in range(i):     # 遍历物品(单词)
                if dp[j] and s[j:i] in wordSet:  # 如果s[0:j]可以被拆分为单词并且s[j:i]在单词集合中存在,则s[0:i]可以被拆分为单词
                    dp[i] = True
                    break
        return dp[n]
1
2
3
4
5
6
7
8
9
10
11
12