---

dp专题11 一和零

原创 于 2024-01-12 16:39:38 发布 · 粉丝可见 · 535 阅读 · 7 · 7 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135556071

本题链接： . - 力扣（LeetCode）

题目：

思路：

由题意，这里有两个特征，要求满足选取的字符串总和中，0的个数和1的个数分别不超过m个0 和 n个 1，问选取的字符串最多有多少个。

又是典型的背包问题，这里我们选取的个数变成了两个，所以这是个二维dp

其中我们明确一下dp[ i ][ j ] 的含义是我们选取的字符串数量，即价值为 1 ，将 n 和 m 作为背包容量即可。

代码详解如下：

class Solution {
public:
    inline int findMaxForm(vector<string>& strs, int m, int n) 
{
	vector<vector<int>>dp(101,vector<int>(101,0));	// 根据题目范围开辟极限大小
	
	for(string &i:strs)		// 遍历我们是否要选取的字符串，  
	{
		int one = 0,zero = 0;	// 统计该字符串的 0  和  1  的数量
		for(char &j:i) 
			if(j - '0') ++one;
			else ++zero;
		
		// 遍历 容量
		for(int j = m;j >= zero;--j)
		{
			for(int k = n;k >= one;--k)
			{
				dp[j][k] = max(dp[j][k],dp[j - zero][k - one] + 1);		// 推导判断是否选取
			}
		}
	}
	return dp[m][n];	// 返回选取字符串最多的数量
}
};

最后提交：