// @Title: 一和零 (Ones and Zeroes)
// @Author: qisiii
// @Date: 2024-09-27 00:39:36
// @Runtime: 18 ms
// @Memory: 40.9 MB
// @comment: 动态规划：子集个数可以理解为价值，每个字符串价值为1，这样子就是最大价值。
// @flag: GREEN
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j]中刚好满足i个0和j个1
        int[][] dp=new int[m+1][n+1];
        //这层循环可以理解为物品
        for(String str:strs){
            int zeroNum=0,oneNum=0;
            for(char c:str.toCharArray()){
                if(c=='0'){
                    zeroNum++;
                }else{
                    oneNum++;
                }
            }
            //0和1的数量可以理解为重量
            //这里之所以倒序是因为当选择了当前元素i，额外计算的是i-1个的情况，可以理解为前一张二维表的状况，也就是str(i-1)对应的dp表
            for(int i=m;i>=zeroNum;i--){
                for(int j=n;j>=oneNum;j--){
            // for(int i=zeroNum;i<=m;i++){
            //     for(int j=oneNum;j<=n;j++){
                    dp[i][j]=Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
}