Leetcode|01背包|474. 一和零（二维01背包）

1 动态规划（二维01背包）

【dp[i][j]数组含义】：容量0的个数最多为i且1的个数最多为j的情况下，两个维度容量的背包下最多的子集数 【状态转移方程】：dp[i][j] = max(dp[i][j], dp[i - cont0][j - cont1] 1)

代码语言：javascript复制

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int size = strs.size();
        vector<vector<int>> dp(m   1, vector<int>(n   1, 0));
        for (int k = 0; k < size; k  ) {         // 遍历物品
            int cont0 = 0, cont1 = 0;
            for (auto& ch : strs[k]) {
                if (ch == '0') cont0  ;
                else cont1  ;
            }
            for (int i = m; i >= cont0; i--)     // 遍历容量（倒序）
                for (int j = n; j >= cont1; j--) 
                    dp[i][j] = max(dp[i][j], dp[i - cont0][j - cont1]   1);      
        }           
        return dp[m][n];
    }
};

dp max 动态规划 数组

0 人点赞