dp专题11 一和零

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

最后提交：