本文主要是介绍9.11一和零（LC474-M），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法：
本题中strs 数组里的元素就是物品，每个物品都是一个！
而m 和 n相当于是一个背包，两个维度的背包。
理解成多重背包的同学主要是把m和n混淆为物品了，感觉这是不同数量的物品，所以以为是多重背包。
但本题其实是01背包问题！
只不过这个背包有两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品。
装满重量为m（m个0）和重量为n（n个1），两个维度的背包，最多能装多少物品
动规五部曲：
1.确定dp数组以及下标含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2.确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
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]）。
3.dp初始化
01背包的dp数组初始化为0就可以。
因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
4.确定遍历顺序
遍历背包容量，要倒序遍历
那个遍历背包容量的两层for循环先后循序有没有什么讲究？
没讲究，都是物品重量的一个维度，先遍历哪个都行！
5.举例推导dp数组
以输入：["10","0001","111001","1","0"]，m = 3，n = 3为例
正确代码：
class Solution {public int findMaxForm(String[] strs, int m, int n) {int dp[][] = new int[m+1][n+1];for (String str:strs){int num0 = 0;int num1 = 0;for (char ch : str.toCharArray()){if (ch=='0') {num0 ++;}else {num1++;}}for (int i=m; i>=num0; i--){for (int j=n; j>=num1; j--){dp[i][j] = Math.max(dp[i][j], dp[i-num0][j-num1]+1);}}}return dp[m][n];}}注意：
1.for (String str:strs){}
在这个特定的背包问题中，我们需要遍历每个字符串，以便计算出其中 0 和 1 的数量，然后根据这些数量进行动态规划的处理。
2.for (char ch : str.toCharArray()){}
这一步是用来遍历字符串 `str` 中的每个字符。这是因为我们需要统计字符串中 0 和 1 的个数，以便在动态规划的过程中使用这些统计数据。
通过将字符串转换为字符数组，我们可以逐个检查每个字符，然后统计其中 0 和 1 的个数。这个步骤是为了确保我们能够准确地计算出每个字符串中 0 和 1 的数量，从而在动态规划的过程中正确地更新状态数组。
时间空间复杂度：
- 时间复杂度: O(kmn)，k 为strs的长度
- 空间复杂度: O(mn)
这篇关于9.11一和零（LC474-M）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
