Force Buckle: 474. Ones and zeros

力扣：474.一和零
题目：
给你一个二进制字符串数组 strs 和两个整数 m 和 n .

请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 .
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 .

dp数组含义：
dp[i][j] :0~n个物品放入容量为i个0,j个1的背包中的最大价值

递归公式：
dp[i][j] = max(dp[i][j],dp[j-current value0][j-current value1]+1)

初始化：
dp【i】【j】Either choose the original onedp【i】【j】（即初始化的dp【i】【j】）Either select the newly calculated value,The larger of the two will be chosen.

• 如果dp【i】【j】is to choose the originaldp【i】【j】即初始化的dp【i】【j】,And because at this time it is from the number of items0开始遍历,By meaning its value should be0.
• 如果dp【i】【j】The selected value is the newly calculated value,dp【i】【j】is to choose the larger value from the two,Then this is initializeddp【i】【j】cannot be greater than the newly calculated value,The newly calculated value is always greater than0.所以初始化的dp【i】【j】为0即可.

遍历顺序：
Iterate over all possibilities of the backpack weight
遍历1items into a backpack of all possible weights
遍历2items into a backpack of all possible weights
遍历nitems into a backpack of all possible weights,Only then can it be ensureddp【i】【j】选择的是dp[j-zeronum][j-onenum]+1的时候,This value is known.
Just make sure at this pointdp【i】【j】选择的是dp[j-zeronum][j-onenum]+1的时候,This value is known,那么先遍历i,j都可以.

for(string str: strs){
    
            int onenum = 0,zeronum = 0;
            for(char c: str){
    
                if(c=='0') zeronum++;
                else onenum++;
            }
            for(int i = m; i >= zeronum; --i){
    
                for(int j = n; j >= onenum; --j)
                {
    
                    dp[i][j] = max(dp[i][j],dp[j-zeronum][j-onenum]+1);
                }
            }
        }