您现在的位置是：首页 >技术杂谈 >leetcode 474.一和零 （01背包 二维网站首页技术杂谈

。。想不到

这里涉及到三个变量： 0 的个数，1 的个数，背包中的数量

所以不能压缩成一维的 01背包

1. dp[ i ] [  j ] 的含义

        下标：i 表示 0 的数量，j 表示 1 的数量

        值：表示当前背包的放入字符串的最大数量

2.递推公式

         dp[i][j] = max(dp[i][j], dp[i - zeroNums][j - oneNums] + 1)

        不放入当前的字符串：dp[i][j]

        放入当前的字符串，且当前字符串中的 0 的数量为 zeroNums，1 的数量为 oneNums：

        dp[i - zeroNums][j - oneNums] + 1

        这个 + 1 就是表示背包中多了一个字符串

3.初始化

       dp[0][0] = 0 当前没有放入任何东西，其它的跟之前题一样，初始化成最小的非负整数

4. 遍历顺序

        物品正序

        背包倒序：因为也是要使用到之前的 dp[i - zeroNums][j - oneNums] 的状态

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 zeroNums = 0, oneNums = 0;
           // 计算每个字符串的 0 1 个数
            for(char c : str)
            {
                if(c == '0')
                    zeroNums++;
                else
                    oneNums++;
            }
            
            // 倒序遍历，但这里的双层循环遍历顺序没有讲究
            for(int i = m ; i >= zeroNums; i--)
            {
                for(int j = n ; j >= oneNums; j--)
                    dp[i][j] = max(dp[i][j], dp[i - zeroNums][j - oneNums] + 1);
            }
        }

        return dp[m][n];
    }
};