动态规划—-一和零 Posted on 2021-09-07 00:00:00 2021-09-07 00:00:00 by Author 摘要 给定多个二进制字符串，你能在限定的条件下找出最多的子集个数，使得这些子集满足题目所给的要求吗？？？？ # 动态规划---一和零 1. 题目描述 - 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。 - **提示：** - 1 <= strs.length <= 600 1 <= strs[i].length <= 100 strs[i] 仅由 '0' 和 '1' 组成 1 <= m, n <= 100 2. 示例描述 - 示例一 ```java 输入：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 。 ``` - 示例二 ```java 输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。 ``` 3. 解题思路 - 首先对于本题而言，首先考虑到的是找出每个字符串中0与1的个数，这是非常容易实现的。接下来，就要考虑在该字符串应该放在那个集合中才能即满足题意又能保证集合个数最大。 - 这里定义一个大小为(m+1)*(n+1)的dp数组，dp [i] [j ]的含义是组成i个0，j个1的子集的最大个数。那么对于一个字符串而言，str1其中包x个0，y个1，那么如果x与y的值都不大于题目所要求的m个0，n个1的要求，那么该字符串可以放入集合中，那么具体放入那个集合中，这就需要判断，如果dp[i-x] [j-y]集合中加入该字符串(dp[i-x] [j-y]表示的是组成(i-x)个1与(j-y)个0的集合最大个数，如果再把有x个0，y个1放入dp[i-x] [j-y]中，那么就组成i个0,j个1这也是我们需要计算的值)，此时dp[i-x] [j-y]+1的个数大于dp[i] [j]的个数，那么dp[i] [j]就为dp[i-x] [j-y]+1，因为题目要求找出最大的子集个数。所以这里的递推公式就为:dp[i] [j] =Math.max(dp[i-x] [j-y]+1,dp[i] [j])。 - 具体实现如下代码所示。 4. 代码示例 ```java public int findMaxForm(String[] strs, int m, int n) { //定义一个(m+1)*(n+1)的dp矩阵 //dp[i][j]表示组成有i个0，j个1的子集有多少个 int dp[][] = new int[m + 1][n + 1]; for (int i = 0; i < strs.length; i++) { //分别找出所遍历的字符串中零与一的个数 int zeroNum = searchNumber(strs[i], '0'); int oneNum = searchNumber(strs[i], '1'); for (int k = m; k >= zeroNum; k--) { for (int l = n; l >= oneNum; l--) { //找出组成k个0，l个1的最大子集个数是多少 dp[k][l] = Math.max(dp[k - zeroNum][l - oneNum] + 1, dp[k][l]); } } } //返回题目所给的组成m个0，l个1的最大子集的个数 return dp[m][n]; } /** * 根据所给的字符，查找字符串中包含字符的个数 */ public int searchNumber(String s, char character) { int result = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == character) result++; } return result; } ```
{{ item.content }}
{{ child.content }}