1、背包问题

一、01 背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。这是标准的背包问题。但是力扣上没有标准的背包问题，有的只是一些变形问题。

但是只有基本的背包问题理解清楚，其他的变形问题才能够完全明白，因此我们先拿标准的背包问题进行分析。

重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

二维数组

问背包能背的物品最大价值是多少？

按照动规5部曲的思路进行分析

• 确定dp数组的含义

  • dp[i][j]指的是背包容量为j,0-i件物品任取，背包所能获取的最大价值。i指的是物品、j指的是背包

• 确定递归公式

  • 能获取的价值在于第i个物品要不要取
  • 取得话为dp[i-1][j-weight[i]]+value[i]
  • 不取的话dp[i-1][j]
  • dp[i][j]能获取的最大价值就是dp[i][j]=max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

• dp数组初始化

  • 当背包容量为0时，dp[i][0]一定为0
  • 当物品为0时，也就是存放物品编号为0时，各个容量的背包所能存放的最大价值
    • j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
    • j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

• dp数组的遍历顺序

  • 由于dp[i][j]是由dp[i-1][j-weight[i]]推导出来，我们可以确定dp[i][j]是由它的左上角得出来的，因此需要从左到右，从上到下进行遍历
  • 那么物品和背包的遍历顺序有影响吗？
    • 二维数组是没有影响的，因为无论是先物品还是先背包都是先得到左上角的值

代码

def bag01(weight: List[int], value: List, bag_value: int):
    dp = [[0] * (bag_value + 1) for _ in range(len(weight))]

    for j in range(weight[0], bag_value + 1):
        dp[0][j] = value[0]

    for i in range(1, len(weight)):
        for j in range(bag_value + 1):
            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])
    print(dp)
    return dp[-1][-1]

一维滚动数组

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

动规五部曲

• dp数组含义：dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

• 递推公式：dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的

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

• 一维dp数组初始化

  • 容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
  • dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
  • 、

• 遍历顺序

  • 先物品再背包，背包倒叙
  • 倒序遍历是为了保证物品i只被放入一次！

  def bag01_1(weight: list, value: list, bag_weight: int):
      dp = [0]*(bag_weight+1)
      for i in range(len(weight)):
          for j in range(bag_weight, weight[i]-1, -1):
              dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
      print(dp)
  
  bag01_1([1, 3, 4], [15, 20, 30], 4)
  

01背包的变形

01背包题目在力扣中没有原题，有的只是一些变形题目。

416. 分割等和子集——weight==value

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

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 == 1:
            return False

        count = total // 2
        dp = [0] * (count + 1)
        for i in range(len(nums)):
            for j in range(count, nums[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
        print(dp)
        return dp[-1] * 2 == total

1049. 最后一块石头的重量 II——weight==value

有一堆石头，用整数数组 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

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        size = total // 2

        dp = [0] * (size + 1)
        for i in range(len(stones)):
            for j in range(size, stones[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
        print(dp)
        return total - (dp[-1] * 2)

494. 目标和 ——01背包组合dp[j]+=dp[j-nums[i]]

给你一个非负整数数组 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

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        """
        思路
        left + right = total
        left - right = target
        right = left - target
        left + left - target = total
        left = (total + target)/2
        if target > total or -target > total:
            rerurn 0
        if (total + target) % 2 == 1:
            return 0
        """
        total = sum(nums)
        if target > total or -target > total:
            return 0
        if (total + target) % 2 == 1:
            return 0
        size = (total + target) // 2
        dp = [0] * (size + 1)
        dp[0] = 1
        for i in range(len(nums)):
            for j in range(size, nums[i] - 1, -1):
                dp[j] += dp[j - nums[i]]
        print(dp)
        return dp[-1]

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 。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for s in strs:
            count0 = s.count("0")
            count1 = s.count("1")
            for i in range(m, count0 - 1, -1):
                for j in range(n, count1 - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - count0][j - count1] + 1)
        print(dp)
        return dp[-1][-1]

二、完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

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

对于完全的完全背包问题，物品和背包的遍历顺序是没有影响的，但是这也是只是针对于完全背包问题。但是针对于求组合问题和排序问题，遍历顺序还是有很多的注意点的。

组合问题先物品再背包

排列问题先背包再物品

组合和排列问题区别为，组合是不管顺序的，排序是需要关心顺序的

标准的完全背包问题的递推公式为dp[j] = max(dp[j], dp[j-witght[i]]+value[i])

对于完全背包的求组合和排列问题都是dp[j]+=dp[j-nums[i]]

518. 零钱兑换 II——完全背包求组合问题

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

思路：

• [2,2,1]和[1,2,2]是没有区别的所以求得是组合问题
• 物品为coins，背包大小为amount,求得是装满背包有多少种方法，由于零钱是可以重复使用的，所以这是完全背包问题

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # 求得是组合问题，[2,2,1]和[1,2,2]是没有区别的，因此需要先物品再背包
        # 组合和排列的递推公式都是dp[j] += dp[j-nums[i]]
		# 这里dp数组长度需要初始化为背包大小，由于需要包括amount,所以需要加一
        dp = [0] * (amount + 1)
        # 求组合问题，dp[0]一定为1，可以理解为装满背包大小为0的背包需要1个方法
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(coins[i], amount + 1):
                dp[j] += dp[j - coins[i]]
        print(dp)
        return dp[-1]

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, 1, 2)、(1, 2, 1)在这里算不同的组合，所以这里求的是排列问题，遍历顺序为先背包再物品

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # 这里求的是排列问题
        dp = [0] * (target + 1)
        dp[0] = 1
        for j in range(1, target + 1):
            for i in range(len(nums)):
                if j >= nums[i]:
                    dp[j] += dp[j - nums[i]]
        print(dp)
        return dp[-1]

完全背包排列组合问题总结

• 排列：先背包再物品
• 组合：先物品再背包
• dp公式都是：dp[j]+=dp[j-nums[i]]
• 初始化都是dp[0] = 1
• dp数组长度都是背包大小

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就是背包，问凑满这个背包最少有多少物品？

标准的背包问题求得是装满背包的最大价值，这里求得是装满背包的最小价值。所以我们需要再初始值和递推公式上稍微做点改变。

初始值，就不能为0了，因为是求得最小值所以我们可以初始为最大值。dp[0]我们可以初始为0，同样代表着背包大小为0的最小价值为0

class Solution:
    def numSquares(self, n: int) -> int:
        # dp[j]：和为j的完全平方数的最少数量为dp[j]
        if n == 1:
            return 1

        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        # 这里i的范围为n//2+1就可以了
        for i in range((n // 2) + 1):
            for j in range(i**2, n + 1):
                if j >= i**2:
                    dp[j] = min(dp[j], dp[j - i**2] + 1)
        # print(dp)
        return dp[-1]

139. 单词拆分——

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

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

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

拆分时可以重复使用字典中的单词，说明就是一个完全背包！

dp[j] : 字符串长度为j的话，dp[j]为true，表示可以拆分为一个或多个在字典中出现的单词。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 背包为字符串的长度len(s)
        # 物品为word
        # 求得是任取words中的字符串是否可以装满背包s
        # 因为words中的字符一定要按照某种顺序才能装满字符串，因此是求得排列问题
        # 排列问题是先背包后物品

        dp = [False] * (len(s) + 1)
        dp[0] = True

        for j in range(1, len(s) + 1):
            for i in range(j):
                if dp[i] and s[i:j] in wordDict:
                    dp[j] = True
                    break
        print(dp)
        return dp[-1]