🌕🌕🌗 474. 一和零

难度: 🌕 🌕 🌗

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // 思路：
        // 背包问题
        // dp[i] = dp[i - nums[j]] + 1, dp[i]
        // 统计每个字符串的 0 & 1 个数
        int len = strs.length;
        int[][] array = new int[len][2];
        for(int i = 0; i < len; i ++) {
            String s = strs[i];
            int[] tmp = zeros(s);
            array[i][0] = tmp[0];
            array[i][1] = tmp[1];
        }
        // dp
        int[][] dp = new int[m + 1][n + 1];
        // 往背包中一个个放入物品进行尝试
        for(int j = 0; j < len; j ++) {
            // 当背包的容量降低到某种程度之后，再小的容量肯定也放不下该物品了，因此即使止损
            for(int p = m; p - array[j][0] >= 0; p --) {
                for(int q = n; q - array[j][1] >= 0; q --) {
                    dp[p][q] = Math.max(dp[p][q], dp[p - array[j][0]][q - array[j][1]] + 1);
                }
            }
        }
        return dp[m][n];
    }

    private int[] zeros(String s) {
        int len = s.length();
        int[] res = new int[] {0, 0};
        for(char c : s.toCharArray()) {
            if(c == '0') {
                res[0] ++;
            } else {
                res[1] ++;
            }
        }
        return res;
    }
}

---

输出