dp专题11 一和零

发布时间:2024-01-12 17:47:15

本题链接:. - 力扣(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];	// 返回选取字符串最多的数量
}
};

最后提交:

文章来源:https://blog.csdn.net/hacker_51/article/details/135556071
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。