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也就是这两个维度的背包容量了，然后就是拓展二维就好。

原文地址：https://blog.csdn.net/Ricky_youngone/article/details/142769464

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！