Leetcode 474. Ones and Zeroes

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Note:
The given numbers of 0s and 1s will both not exceed 100
The size of given string array won’t exceed 600.

Example1:
Intput: Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3
Output: 4
01背包问题

Solution1: Dynamic Programing
类似01背包问题，采用dp[i][j], i表示采用了i个0， j表示j个1， 对于每个string，可以决定采用或者不采用，放入包里，那么决定于
i， j减去当前需要的还能装入的最大值， 所以dp公式： dp[i][j] = max(dp[i-i_need][j-j_need] + 1, dp[i][j]);
因为字符串的顺序是有长有短，不按顺序，所以并不能确定dp[i-i_need][j-j_need]已经更新到最大，所以不能滚动数组操作??（可以）
对于每个字符采用一个新二维矩阵。

Solution2: DP 采用单二维矩阵解法，空间复杂度为O(mn)
更新次序从bottom right往top left更新，每次会在更大容量的包dp[i][j]中从左向右加
1， 如果从左上到右下更新，会重复计算。
核心代码：
for(int i = m; i >= numZeros; i–){
for(int j = n; j >= numsOnes; j–){
memo[i][j] = max(memo[i][j], memo[i-numZeros][j-numOnes]+1);
}
}
return memo[m][n];