动态规划-01背包问题（纯01背包、分割等和子集、最后一块石头的重量II、目标和、一和零）

心已赠人 2023-09-25 17:19 77阅读 0赞

1.  ## 01 背包问题（二维数组） ##

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。**每件物品只能用一次**，求解将哪些物品装入背包里物品价值总和最大。

例子：

背包最大重量为4。

物品为：

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

### 分析： ###

可以直接用暴力解法，每个物品只有两种状态，取或不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是 O(2^n)，n 表示物品数量

因为时间复杂度是指数的，所以才要用动态规划来做

**动态规划五步走**，这道题使用 二维 dp 数组 来做

1.  **状态定义：dp【i】【j】表示从下标 0 到 i 的物品任意取，放进容量为 j 的背包，价值总和最大是多少**

![39e67cda70dd1aa225444649ad41963e.png][]

1.  **状态转移：dp\[i\] \[j\] = max(dp\[i-1\] \[j\]，dp\[i-1\] \[j - weight\[i\]\] + value\[i\])**

再次强调：dp【i】【j】的含义是，从下标为 0 到 i 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。

那么可以有两个种情况，

*  **不放物品 i ：** **dp\[i-1\] \[j\]** ，也就是背包容量为 j，里面不放物品 i 的最大价值就是 dp\[i-1\] \[j\]，也可以这样理解当物品 i 的重量大于背包 j 的重量时，物品 i 无法放入背包中，所以背包内的价值依然和前面相同。

*  **放物品 i ：dp\[i-1\] \[ j - weight\[i\] \] + value\[i\]**，可以理解为不放 i 的时候最大价值为 dp\[i-1\] \[ j - weight\[i\] \]，然后把物品 i 放进来后，要在不放 i 的最大价值基础之上加上 i 的价值，这样就是背包放物品 i 得到的最大价值。

所以，就是取这两种情况中价值最大的。

1.  初始化：dp\[i\] \[0\] = 0

当背包容量 j 为 0 时，也就是 dp\[i\] \[0\]，无论是选哪个物品，背包价值总和一定为 0。

![899de66e408703840fc3ba3cd0dd68c1.png][]

然后通过分析状态转移方程，dp\[i\] \[j\] = max(dp\[i-1\] \[j\]，dp\[i-1\] \[j - weight\[i\]\] + value\[i\])，可以看出 i 是由 i -1 推导出来的，那么 i = 0 时就一定要初始化。

dp\[0\] \[j\] ，也就是 i = 0 时，存放编号为 0 的物品的时候，各个容量的背包所能存放的最大价值。

当 j < weight\[0\] 的时候，也就是背包的容量比编号为 0 的物品重量小的时候，dp\[0\] \[j\] = 0;

当 j > weight\[0\] 时，dp\[0\] \[j\] = value\[0\]，因为背包容量可以放下编号为 0 的物品。

![39db09fb9f353426d2bd62a00e8eff84.png][]

// 背包容量 < 编号为 0 的物品重量，就初始化为 0
 for(int j = 0; j < weight[0]; j++) {
 	dp[0][j] = 0;
 }
 for(int j = weight[0]; j <= bagweight; j++) {
 	dp[0][j] = value[0];
 }

此时已经把 dp\[0\] \[j\] 和 dp\[i\] \[0\] 都初始化了，那么其他下标应该怎么初始化

![66edf09174dc94a4cd6061076584aac6.png][]

1.  遍历顺序：

题中可以遍历物品或背包重量，这两种都可以，只不过先遍历物品更好理解

for(int i = 1; i < weight.size; i++) { // 编号为0 的物品，已经被初始化了
 	for(int j = 0; j <= bagweight; j++) {
 		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]);
 		}
 	}
 }

也可以遍历背包重量

for(int j = 0; j <= bagweight; 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]);
 		}
 	}
 }

这两种遍历的方式都可以，因为本质都是遍历到左上角或上面的方向。

### 代码： ###

// 01 背包
 /*
 * @param weight: 物品的重量
 * @param value: 物品的价值
 * @param bagSize: 背包的容量
 */
 public static void testWeightProblem(int[] weight,int[] value,int bagSize) {
 // 创建 dp 数组
 int goods = weight.length;
 int[][] dp = new int[goods][bagSize+1];
 
 // 初始化 dp 数组
 for (int j = weight[0]; j <= bagSize; j++) {
 dp[0][j] = value[0];
 }
 
 // 填充 dp 数组
 for (int i = 1; i < weight.length; i++) {
 for (int j = 1; j <= bagSize; j++) {
 if (j < weight[i]) {
 // 当背包容量小于当前物品 i 的重量时，i 不放入背包
 // 那么前 i-1 个物品就是当前背包能放下的最大价值
 dp[i][j] = dp[i-1][j];
 } else {
 // 此时背包容量可以放下物品 i
 // 有两种情况，不放物品 i，放物品 i
 dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);
 }
 }
 }
 
 // 打印 dp 数组
 for (int i = 0; i < goods; i++) {
 for (int j = 0; j <= bagSize; j++) {
 System.out.print(dp[i][j] + "\t");
 }
 System.out.println("\n");
 }
 }
 
 public static void main(String[] args) {
 int[] weight = {1,3,4};
 int[] value = {15,20,30};
 int bagSize = 4;
 testWeightProblem(weight,value,bagSize);
 }

## 2. 01 背包问题（一维数组-每件物品只放一次） ##

题目还是上面的题目，只不过这里优化一下，把二维数组的解法优化为一维数组

背包最大重量为4

### 思路： ###

先来回顾一下二维数组解法中，dp\[i\] \[j\] 的含义，编号为 0 到 i 的物品，任取放入容量为 j 的背包中的最大价值 dp\[i\] \[j\]。

状态转移方程：dp\[i\] \[j\] = Math.max( dp\[i-1\] \[j\]，dp\[i-1\] \[j- weight\[i\]\] + value(i) )

如果把 dp\[i-1\] 那一层拷贝到 dp\[i\] 上，表达式可以是：dp\[i\] \[j\] = Math.max( dp\[i\] \[j\]，dp\[i\] \[j- weight\[i\]\] + value(i) ) ，与其这样拷贝下来，不如直接用一个一维数组，只用 dp\[j\]。

这个一维数组也叫滚动数组，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

**下面根据动态五步走分析：**

1.  状态定义：dp\[j\] 表示：容量为 j 的背包，所放物品的最大价值可以为 dp\[j\]。

1.  状态转移：dp\[j\] = Math.max(dp\[j\]，dp\[j - weight\[i\]\] + value\[i\] )

和二维数组意思一样，一种是不放物品 i ，此时背包容量还是 j，价值为 dp\[j\]

一种是放物品 i，先要将背包的容量减去物品 i 的重量，也就是 dp\[j - weight\[i\]\] ，然后加上物品 i 的价值 value\[i\]。

最后状态转移，求两种情况中最大的。

1.  初始化；dp\[0\] = 0

根据状态转移方程来分析，j 表示背包容量，所以当容量为 0 时，价值为0，也就是 dp\[0\] = 0。因为状态转移时，是取最大的，所以其他下标初始化时，为 0 就可以，后面状态转移会把 0 覆盖了。

1.  遍历顺序：从大到小

这个的遍历顺序和二维数组写法的遍历顺序是不一样的。

因为二维数组的写法，dp\[i\] \[j\] 是通过上一层 dp\[i-1\] \[j\] 计算的，本层的 dp\[i\] \[j\] 是不会被覆盖的。

而一维数组的写法，倒序遍历是为了保证物品 i 只会被放入一次，如果是正序遍历的话，物品 0 就会被重复放入多次。

> 比如，物品 0 的重量 weight\[0\] = 1, 价值 value\[0\] = 15  
> **如果是正序遍历，**  
> dp\[1\] = dp\[1 - weight\[0\]\] + value\[0\] = 15 (放入物品 0，背包的容量减去物品 0 的重量，此背包的价值为 dp\[0\] = 0， 然后加上物品 0 的价值 value\[0\])  
> dp\[2\] = dp\[2 - weight\[0\]\] + value\[0\] = 30  
> 因为 物品 1 的重量为 3，所以当背包容量为 2 时，物品 1 还是放不进去，只能放物品 0，可以看到 dp\[2\] = 30，说明物品 0 被放入了 2 次， **所以不能正序遍历。**  
> **如果是倒序遍历，**  
> 倒序也就是先算 dp\[2\]  
> dp\[2\] = dp\[2 - weight\[0\]\] + value\[0\] = 15 (因为初始化 dp\[1\] = 0，所以当背包容量为 2 时，只放入一次物品 0 )  
> dp\[1\] = dp\[1 - weight\[1\]\] + value\[0 = 15  
> 所以从后往前循环，每次取得的状态不会和之前的状态重合，这样每种物品就只取一次了

for(int i = 0; i < weight.length; i++) { // 遍历物品
 	for(int j = bagWeight; j >= weight[i]; j--) {
 		dp[j] = Math.max(dp[j],dp[j - weight[i]]+value[i]);
 	}
 }

![e325ceb6cc8848fa07683f94cb8601c1.png][]

还要注意的一个点是，两个 for 循环嵌套，代码中必须是先遍历物品然后遍历背包容量。

不能先遍历背包容量再遍历物品，因为一维 dp 的写法，背包容量一定是要倒序遍历的，如果遍历背包容量放在上一层，那么每个 dp\[j\] 就只会放入一个物品

![7c12d41c4da725b02ef803d7a313f461.png][]

1.  返回值：dp\[bagWeight\]

### 代码： ###

// 滚动数组（一维数组）
 public static void testWeightBagProblem(int[] weight,int[] value,int bagWeight) {
 int wLen = weight.length;
 int[] dp = new int[bagWeight+1];
 // 遍历顺序，先遍历物品，再遍历背包容量
 for (int i = 0; i < weight.length; i++) {
 for (int j = bagWeight; j >= weight[i]; j--) {
 dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
 }
 }
 // 打印 dp 数组
 for (int j = 0; j <= bagWeight; j++) {
 System.out.print(dp[j] + " ");
 }
 }
 
 public static void main(String[] args) {
 int[] weight = {1,3,4};
 int[] value = {15,20,30};
 int bagSize = 4;
 // testWeightProblem(weight,value,bagSize);
 testWeightBagProblem(weight,value,bagSize);
 }

## 3. 分割等和子集 ##

**题目链接：**[416. 分割等和子集 - 力扣（LeetCode）][416. _ - _LeetCode]

给你一个 只包含正整数 的 非空 数组 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 背包问题，而这道题中物品重量和价值的数组都是 nums 数组。

这道题要求的是判断是否有总和为 sum/2 的两个子集，要用 01背包，就要明确

*  背包的体积为 sum/2

*  背包要放入的物品重量为元素的数值，价值也为元素的数值

*  背包如果刚好装满，说明找到了总和为 sum/.2 的子集

*  背包中每一个元素是不可重复放入的

### 代码： ###

/** 01 背包问题
 1. 状态定义：dp[j]：容量为 j 时，背包的最大价值
 2. 状态转移；dp[j] = max(dp[j],dp[j-nums[i]]+nums[0])
 本道题的01背包问题，物品的重量和价值都对应 nums 数组
 3，初始化：dp[j] = 0
 4. 遍历顺序：从大到小（倒序，从而保证物品遍历一次（nums元素遍历一次））
 5. 返回值：如果背包价值 == sum/2 返回 true
 */
 public boolean canPartition(int[] nums) {
 if(nums == null || nums.length == 0) {
 return false;
 }
 int n = nums.length;
 int sum = 0;
 for(int x : nums) {
 sum += x;
 }
 // 如果和为奇数，就不能分割
 if(sum%2 != 0) {
 return false;
 }
 int target = sum/2;
 int[] dp = new int[target+1];
 for(int i = 0; i < nums.length; i++) { // 物品
 for(int j = target; j >= nums[i]; j--) { // 容量
 dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
 }
 }
 for(int i = 0; i < dp.length; i++) {
 System.out.print(dp[i] + " ");
 }
 return dp[target] == target;
 }

## 4. 最后一块石头的重量 II ##

**题目链接：**[1049. 最后一块石头的重量 II - 力扣（LeetCode）][1049. _ II - _LeetCode]

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

**提示：**

1 <= stones.length <= 30

1 <= stones\[i\] <= 100

### 思路： ###

本道题是，将一堆石头，每次取出两个石头两两相撞，然后得出相撞之后剩下的最小的石头，也可以理解为将石头尽量分成重量相同的两堆，然后进行相撞得出最小的石头，这样也就变成了01背包问题

背包的最大重量为 数组 sum/2

物品的重量和价值都是 stones\[i\]，和上道题的基本是一样的。

不同的是上道题最后返回的是如果 sum/2 和 dp\[target\] 相等了就返回 true

这道题是要返回最后相撞最小的石头，因为 target = sum/2 是向下取整的，所以sum - dp\[target\] 是一定大于 dp\[target\] 最后返回 sum - 2\*dp\[target\]

### 代码： ###

/** 01-背包问题
 1. 状态定义：dp[j]：背包容量为 j 时，最大价值为 dp[j]
 2. 状态转移：dp[j] = max(dp[j],dp[j-stones[i]]+stones[i])
 3. 初始化：dp[j] = 0
 4. 遍历顺序：从大到小
 5. 返回值：石头最小的重量
 */
 public int lastStoneWeightII(int[] stones) {
 int n = stones.length;
 int sum = 0, target = 0;
 for(int i = 0; i < n; i++) {
 sum += stones[i];
 }
 target = sum/2;
 int[] dp = new int[target+1];
 dp[0] = 0;
 for(int i = 0; i < n; i++) {
 for(int j = target; j >= stones[i]; j--) {
 dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i]);
 }
 }
 return sum - 2*dp[target];
 }

## 5. 目标和 ##

**题目链接：**[494. 目标和 - 力扣（LeetCode）][494. _ - _LeetCode]

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

### 思路： ###

先分析一下题目，本题要求的就是表达式结果为 target 的数目

这里可以定义 left 为正数的和，right 为负数的和（这里的正数和负数不是数组中的正负，而是题中给这些数字前面加的正负号，来区分的正负，这里的 left 和 right 虽然区分正负，但只是将数字拿出来求和了和正负号无关），

所以就有 target = left - right （target 为 left 和 right 加了正负号之后的和）

sum = left + right (虽然left、right 表示正负的和，但这个只是单纯的和，和正负无关，sum本质上就是数组元素的和)

根据两个公式推导 left = (target + sum)/2

target 和 sum 都是固定的，那么 left 就可以求出来，现在的目标就是在集合 nums 中找出和为 left 的组合，也可以理解为 **装满容量为 left 的背包，有几种方法**，所以 bagSize = left；

还要考虑的问题是，（target+sum）/2 向下取整的问题

如果 sum = 5，target = 2，那么这个是无解的

if((sum+target)%2 == 1) return 0;

同时如果 taget 的绝对值大于 sum，那么这个也是无解的

if(abs(target) > sum) return 0;

这道题也是 **01背包问题，因为每个物品（题目中的1）只用一次**，但是和之前背包问题不同的是，之前都是求容量为 j 的背包，最多能装多少，而现**在是装满有几种方法，这个求的就是一个组合问题**

**动归五步走：**

1.  状态定义：dp\[j\] 表示：填满容量为 j 的背包，有 dp\[j\] 种方法。

也可以定义二维数组的方法，dp\[i\] \[j\] 表示：使用下标 0-i 的 nums\[i\] (相当于下标 0-i 的物品重量)，装满容量为 j 的背包，有 dp\[i\] \[j\] 种方法

1.  状态转移：dp\[j\] += dp\[j - nums\[i\]\]

只要知道 nums\[i\]，凑成 dp\[j\] 就有 dp\[j - nums\[i\]\] 种方法

比如： dp\[j\]，j = 5

*  已经有一个 1 （也就是 nums\[i\] 为 1）的话，有 dp\[4\] 种方法，凑成容量为 5 的背包

*  已经有一个 2 （也就是 nums\[i\] 为 2）的话，有 dp\[3\] 种方法，凑成容量为 5 的背包

*  已经有一个 3 （也就是 nums\[i\] 为 3）的话，有 dp\[2\] 种方法，凑成容量为 5 的背包

*  已经有一个 4 （也就是 nums\[i\] 为 4）的话，有 dp\[1\] 种方法，凑成容量为 5 的背包

*  已经有一个 5 （也就是 nums\[i\] 为 5）的话，有 dp\[0\] 种方法，凑成容量为 5 的背包

所以要知道 dp\[5\] 有多少种方法，就要把所有的 dp\[j - nums\[i\]\] 加起来

1.  初始化：dp\[0\] = 1

比如：数组 nums\[0\] ，target = 0，那么 bagSize = （target+sum）/2 = 0，也就是背包容量为 0 时，数组中的元素 0 无论前面是加法还是减法，都是 1 种方法，所以 dp\[0\] 应该等于 1.

那如果数组 nums\[0,0,0,0,0\]，target = 0 呢

此时最终 dp\[0\] = 32,这也是所以的组合情况，这里的 dp\[0\] 不是我们要初始化的那个 dp\[0\]，dp\[0\] = 32 ，基础是由初始化 dp\[0\] = 1 累加起来的。

1.  遍历顺序：nums 放在外循环，bagSize 放在内循环，并且内循环是倒序

1.  返回值 dp\[bagSize\]

### 代码： ###

/**
 1. 状态定义：dp[j]:背包容量为 j 时，有 dp[j] 种表达式数目
 2. 状态转移：dp[j] += dp[j - nums[i]]
 3. 初始化：dp[0] = 1
 4. 遍历顺序：nums 在外从小到大，bagSize 在内从大到小
 5. 返回值：dp[bagSize]
 */
 public int findTargetSumWays(int[] nums, int target) {
 int sum = 0;
 for(int x : nums) {
 sum += x;
 }
 if(target < 0 && sum < -target) {
 return 0;
 }
 if((target+sum)%2 != 0) {
 return 0;
 }
 int bagSize = (sum+target)/2;
 if(bagSize < 0) {
 bagSize = -bagSize;
 }
 int[] dp = new int[bagSize+1];
 dp[0] = 1;
 for(int i = 0; i < nums.length; i++) {
 for(int j = bagSize; j >= nums[i]; j--) {
 dp[j] += dp[j - nums[i]];
 }
 }
 return dp[bagSize];
 }

## 6. 一和零 ##

**题目链接：**[474. 一和零 - 力扣（LeetCode）][474. _ - _LeetCode]

给你一个二进制字符串数组 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

### 思路： ###

本道题中 strs 数组中的元素相当于物品，每个物品都是一个，而 m 和 n 相当于是一个背包，两个维度的背包（注意这不是多重背包，多重背包的要求是不同的物品数量不同），所以这道题本质还是一个 01 背包问题。

这道题中背包有两个维度，一个是 m 一个是 n，而不同长度的字符串就是大小不同的物品。

**下面分析动态五步走：**

1.  状态定义：dp\[i\] \[j\]：最多有 i 个 0 和 j 个 1 的 strs 的最大子集的大小为 dp\[i\] \[j\]

1.  状态转移：dp\[i\] \[j\] = max(dp\[i\] \[j\]，dp\[i - zeroNum\] \[j - oneNum\] + 1)

dp\[i\] \[j\] 可以由前一个 strs 中的字符串推导出来，strs 中的字符串有 zeroNum 个 0 ，oneNum 个 1。

dp\[i\] \[j\] 就可以是 dp\[i - zeroNum\] \[j - oneNum\] + 1（因为 dp\[i\] \[j\] 表示的是子集个数，所以当把 strs 中的某个字符串放进去后， 0 和 1 背包中的容量也要减小，然后再加 1，说明这个最大子集长度又增加 1）

然后就可以在遍历过程中，取 dp\[i\] \[j\] 的最大值

所以递推公式：dp\[i\] \[j\] = max(dp\[i\] \[j\]，dp\[i - zeroNum\] \[j - oneNum\] + 1)

对应到之前的一维 01 背包的递推公式，dp\[j\] = max(dp\[j\]，dp\[j - weight\[i\]\] + value\[i\])，所以字符串的 zeroNum 和 oneNum 相当于物品的重量（weight\[i\]）,字符串本身的个数相当于物品的价值(value\[i\])

1.  初始化：dp\[i\] \[j\] = 0

1.  遍历顺序：

之前01背包遍历都是 外层 for 遍历物品，内层 for 遍历背包容量且从后向前。

本道题也是这样，物品就是 strs 中的字符串，背包容量就是 m 和 n

1.  返回值：

### 代码： ###

/**
     1. 状态定义：d[i][j]:背包容量 i个0 j个1时，有dp[i][j]的最大子集
     2. 状态转移：dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)
     3. 初始化：dp[i][j] = 0
     4. 遍历顺序：物品就是 strs 中的字符串，背包容量就是 m 和 n
     物品外层从小到达，容量内层从大到小
     5. 返回值：dp[m][n]
     */
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        int zeroNum = 0,oneNum = 0;
        for(String str : strs) { // 遍历物品编号
            zeroNum = 0;
            oneNum = 0;
            for(char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            for(int i = m; i >= zeroNum; i--) { // 遍历背包容量
                for(int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }

[39e67cda70dd1aa225444649ad41963e.png]: https://img-blog.csdnimg.cn/img_convert/39e67cda70dd1aa225444649ad41963e.png
[899de66e408703840fc3ba3cd0dd68c1.png]: https://img-blog.csdnimg.cn/img_convert/899de66e408703840fc3ba3cd0dd68c1.png
[39db09fb9f353426d2bd62a00e8eff84.png]: https://img-blog.csdnimg.cn/img_convert/39db09fb9f353426d2bd62a00e8eff84.png
[66edf09174dc94a4cd6061076584aac6.png]: https://img-blog.csdnimg.cn/img_convert/66edf09174dc94a4cd6061076584aac6.png
[e325ceb6cc8848fa07683f94cb8601c1.png]: https://img-blog.csdnimg.cn/img_convert/e325ceb6cc8848fa07683f94cb8601c1.png
[7c12d41c4da725b02ef803d7a313f461.png]: https://img-blog.csdnimg.cn/img_convert/7c12d41c4da725b02ef803d7a313f461.png
[416. _ - _LeetCode]: https://leetcode.cn/problems/partition-equal-subset-sum/
[1049. _ II - _LeetCode]: https://leetcode.cn/problems/last-stone-weight-ii/
[494. _ - _LeetCode]: https://leetcode.cn/problems/target-sum/
[474. _ - _LeetCode]: https://leetcode.cn/problems/ones-and-zeroes/