LeetCode474:一和零
题目链接:474. 一和零 - 力扣(LeetCode)
代码如下
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
for(string str : strs)
{
int oneNum = 0, zeroNum = 0;
for(char ch : str)
{
if(ch == '0') oneNum++;
else zeroNum++;
}
for(int i = m; i >= oneNum; i--)
{
for(int j = n; j >= zeroNum; j--)
{
dp[i][j] = max(dp[i][j], dp[i - oneNum][j - zeroNum] + 1);
}
}
}
return dp[m][n];
}
};
这个代码其实也很好的理解为是多维度的01背包问题,也就是说,我们有两个背包容量,去选择价值最大的物品,首先我们需要先遍历这个字符串的数组的每一个字符,先把字符的0和1分别统计下来,然后去统计好oneNum和zeroNum的数值,再去用01背包的递推公式去解开这个问题。
这里要讲一下递推公式是怎么来的,其实这个也就是相当于三维数组了(没优化先),01背包优化之后遍历的时候都需要两层for循环了,所以这个多维度的背包问题,肯定就是需要三重for循环。顾名思义,题目给了最多有m个0和n个1也就是这两个维度的背包容量了,然后就是拓展二维就好。