背包问题

## 1 含义

1. **给定一个背包容量 $target$**，**再给定一个数组**$nums$（物品），**能否按一定方式选取 $nums$ 中的元素得到 $target$**。
2. 需要注意的是：
   1. **背包容量 $target$ 和物品 $nums$ 的类型可能是数**，**也可能是字符串**。
   2. $target$**可能题目已经给出**（显式），**也可能是需要我们从题目的信息中挖掘出来**（非显式）（常见的非显式 $target$ 比如 $sum / 2$ 等）。
   3. **选取的方式**有常见的以下几种：
      1. **每个元素选一次**。
      2. **每个元素选多次**。
      3. **选元素进行排列组合**。

## 2 分类及解题模板

1. 常见的背包类型有以下几种：
   1. **0/1 背包问题**：
      1. **每个元素最多选取一次**。
      2. **外循环 $nums$**，**内循环**（倒序）**$target$**，且 $target \ge num$。
   2. **完全背包问题**：
      1. **每个元素可以重复选择**。
      2. **外循环 $nums$**，**内循环**（正序）$target$，且 $target \ge num$。
   3. **组合背包问题**：
      1. **背包中的物品要考虑顺序**。
      2. **外循环**（正序）**$target$**，**内循环 $nums$**，且 $target \ge num$。
   4. **分组背包问题**：
      1. **不止一个背包**，**需要遍历每一个背包**。
      2. **这个比较特殊**，**需要三重循环**，**外循环背包 $bags$**，**内部两层循环根据题目的要求转化为上面三种背包类型的模板**。
2. 而每个背包问题要求的也是不同的，按照所求问题分类，又可以分为以下几种：
   1. **最值问题**：
      1. **要求最大值或最小值**。
      2. $dp[i] = max/min(dp[i], dp[i - num] + 1)$ 或 $dp[i] = max/min(dp[i], dp[i - num] + num)$。
      3. 一般需要把$dp[i]$初始化为 `Integer.MAX_VALUE`或`Integer.MIN_VALUE`
   2. **存在问题**：
      1. **是否存在**...，**满足**...。
      2. $dp[i] = dp[i] || dp[i - num]$。
      3. 一般需要把$dp[0]$初始化为 `true`。
   3. **组合问题**：
      1. **求所有满足**...**的排列组合**。
      2. $dp[i] += dp[i - num]$。
      3. 一般需要把$dp[0]$初始化为1。

## 3 题目示例

### 3.1 完全背包最值问题

> 题目来源[322. 零钱兑换](https://leetcode-cn.com/problems/coin-change)。

#### 3.1.1 题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

**示例 1：**

```txt
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
```

**示例 2：**

```txt
输入：coins = [2], amount = 3
输出：-1
```

**示例 3：**

```txt
输入：coins = [1], amount = 0
输出：0
```

**示例 4：**

```txt
输入：coins = [1], amount = 1
输出：1
```

**示例 5：**

```txt
输入：coins = [1], amount = 2
输出：2
```

**提示：**

* 1 <= coins.length <= 12
* 1 <= coins[i] <= 231 - 1
* 0 <= amount <= 104

#### 3.1.2 问题分析

1. 该题目属于**完全背包最值问题**，直接套用相应的解题模板即可。

#### 3.1.3 参考代码

```java
/**
 * 322. 零钱兑换
 * @param coins 不同面额的硬币数组
 * @param amount    总金额
 * @return  可以凑成总金额所需的最少的硬币个数
 */
public int coinChange(int[] coins, int amount) {
    int m = coins.length;
    //  dp 数组，其中 dp[i] 表示凑成金额 i 所需的最少的硬币个数
    int[] dp = new int[amount + 1];

Arrays.fill(dp, amount + 1);

dp[0] = 0;
    for (int coin: coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }

return dp[amount] == amount + 1 ? -1 : dp[amount];
}
```

#### 3.1.3 扩展题目

##### 3.1.3.1 [完全平方数](https://leetcode-cn.com/problems/perfect-squares)

###### 3.1.3.1.1 题目

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

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

**示例 1：**

```txt
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
```

**示例 2：**

```txt
输入：n = 13
输出：2
解释：13 = 4 + 9
```

**提示：**

* 1 <= n <= 104

###### 3.1.3.1.2 问题分析

1. **完全平方数最小为 1**，**最大为 $sqrt(n)$**，故**题目转换为在 $nums = [1,2,...,sqrt(n)]$ 中选任意数平方和为 $target = n$**。
2. 该题目属于**完全背包最值问题**，直接套用相应的解题模板即可。

###### 3.1.3.1.3 参考代码

```java
/**
 * 279. 完全平方数
 * @param n 一个正整数
 * @return  和为 n 的完全平方数的 最少数量
 */
public int numSquares(int n) {
    //  dp 数组，其中 dp[i] 表示和为 i 的完全平方数的最少数量
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);

dp[0] = 0;
    for (int num = 1; num <= Math.sqrt(n); num++) {
        for (int i = num * num; i <= n; i++) {
            dp[i] = Math.min(dp[i], dp[i - num * num] + 1);
        }
    }

return dp[n];
}
```

### 3.2 0/1 背包存在性问题

> 题目来源[416. 分割等和子集](https://leetcode-cn.com/problems/partition-equal-subset-sum)。

#### 3.2.1 题目

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

**示例 1：**

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

**示例 2：**

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

**提示：**

* 1 <= nums.length <= 200
* 1 <= nums[i] <= 100

#### 3.2.2 问题分析

1. 该题目等价于**是否存在一个子集**，**其和为 $target = sum / 2$**。
2. 该题目属于**0/1 背包存在性问题**，直接套用相应的解题模板即可。

#### 3.2.3 参考代码

```java
/**
 * 416. 分割等和子集
 * @param nums  只包含正整数的非空数组
 * @return  是否可以将这个数组分割成两个子集，使得两个子集的元素和相等
 */
public boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).sum(), target = sum / 2;
    int m = nums.length + 1;
    //  dp 数组，其中 dp[i] 表示是否可以将原数组分成两个和为 i 的子集
    boolean[] dp = new boolean[target + 1];

//  base case
    //  如果和为奇数，显然无法分成两个等和子集
    if (sum % 2 != 0) {return false;}

dp[0] = true;
    for (int num: nums) {
        for (int i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }

return dp[target];
}
```

### 3.3 0/1 背包组合问题

> 题目来源[494. 目标和](https://leetcode-cn.com/problems/target-sum)。

#### 3.3.1 题目

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

**示例 1：**

```txt
输入：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：**

```txt
输入：nums = [1], target = 1
输出：1
```

**提示：**

* 1 <= nums.length <= 20
* 0 <= nums[i] <= 1000
* 0 <= sum(nums[i]) <= 1000
* -1000 <= target <= 1000

#### 3.3.2 问题分析

1. **假设数组和为 $sum$**，**目标和为 $s$**，**正数和为 $x$**，**负数和为 $y$**，则：

$$
   x + y = sum, x - y = s
   $$

可得：

$$
   x = \frac{s + sum}{2}
   $$
2. 所以该题目可以转换为**从数组**$nums$**中无放回的选取几个数**，**其和等于**$x$**的组合的个数**。
3. 该题目属于**0/1 背包组合问题**，直接套用相应的解题模板即可。

#### 3.3.3 参考代码

```java
/**
 * 494. 目标和
 * @param nums  整数数组
 * @param target    目标整数
 * @return  通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目
 */
public int findTargetSumWays(int[] nums, int target) {
    int m = nums.length;
    int sum = Arrays.stream(nums).sum();
    //  dp 数组，其中 dp[i] 表示 从数组 nums 中无放回选取元素，其和等于 i 的组合的个数
    int[] dp = null;

if ((sum + target) % 2 != 0 || sum < Math.abs(target)) {return 0;}

target = (sum + target) / 2;
    dp = new int[target + 1];
    dp[0] = 1;
    for (int num: nums) {
        for (int i = target; i >= num; i--) {
            dp[i] += dp[i - num];
        }
    }

return dp[target];
}
```

### 3.4 组合背包组合问题

> 题目来源[377. 组合总和 Ⅳ](https://leetcode-cn.com/problems/combination-sum-iv)。

#### 3.4.1 题目

给你一个由 不同 整数组成的数组 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：**

```txt
输入：nums = [9], target = 3
输出：0
```

**提示：**

* 1 <= nums.length <= 200
* 1 <= nums[i] <= 1000
* nums 中的所有元素 互不相同
* 1 <= target <= 1000

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

#### 3.4.2 问题分析

1. 该题目中**顺序不同的序列被视作不同的组合**，即**背包中的物品需要考虑顺序**，所以该题目属于**组合背包组合问题**，直接套用相应的解题模板即可。

#### 3.4.3 参考代码

```java
/**
 * 377. 组合总和 Ⅳ
 * @param nums  不同整数组成的数组
 * @param target    目标整数
 * @return  从 nums 中可以找到的总和为 target 的元素组合的个数
 */
public int combinationSum4(int[] nums, int target) {
    int m = nums.length;
    //  dp 数组，其中 dp[i] 表示从 nums 中可以找到的总和为 i 的元素组合的个数
    int[] dp = new int[target + 1];

dp[0] = 1;
    for (int i = 1; i <= target; i++) {
        for (int num: nums) {
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }

return dp[target];
}
```

### 3.5 完全背包组合问题

> 题目来源[518. 零钱兑换 II](https://leetcode-cn.com/problems/coin-change-2)。

#### 3.5.1 题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

**示例 1：**

```txt
输入：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：**

```txt
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
```

**示例 3：**

```txt
输入：amount = 10, coins = [10]
输出：1
```

**提示：**

* 1 <= coins.length <= 300
* 1 <= coins[i] <= 5000
* coins 中的所有值 互不相同
* 0 <= amount <= 5000

#### 3.5.2 问题分析

1. 该题目属于**完全背包组合问题**，直接套用相应的解题模板即可。

#### 3.5.3 参考代码

```java
/**
 * 518. 零钱兑换 II
 * @param amount    总金额
 * @param coins 不同面额的硬币数组
 * @return  可以凑成总金额的硬币组合数
 */
public int change(int amount, int[] coins) {
    int m = coins.length;
    //  dp 数组，其中 dp[i] 表示可以凑成总金额为 i 的硬币组合数
    int[] dp = new int[amount + 1];

dp[0] = 1;
    for (int coin: coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

return dp[amount];
}
```

## 参考文献

1. [ 一篇文章吃透背包问题！（细致引入 + 解题模板 + 例题分析 + 代码呈现）](https://leetcode-cn.com/problems/coin-change-2/solution/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-2xkk)。
2. [322. 零钱兑换](https://leetcode-cn.com/problems/coin-change)。
3. [416. 分割等和子集](https://leetcode-cn.com/problems/partition-equal-subset-sum)。
4. [494. 目标和](https://leetcode-cn.com/problems/target-sum)。
5. [279. 完全平方数](https://leetcode-cn.com/problems/perfect-squares)。
6. [377. 组合总和 Ⅳ](https://leetcode-cn.com/problems/combination-sum-iv)。
7. [518. 零钱兑换 II](https://leetcode-cn.com/problems/coin-change-2)。