LeetCode 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:

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

Example 1:

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

Example 2:

Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

---

给定一个0,1字符串数组，问最多能从中选出多少个字符串，使得所有字符串的’0’和’1’的个数不超过m和n。 明显的背包问题，常规的0/1背包是若干个商品，费用不超过某个值。这里的背包是若干个商品，费用不超过m和n，也就是有两个限制。本题可以用二维背包解决，和一维背包很类似，都是假设某个商品要还是不要，然后更新dp数组。只不过这里有两个限制条件，所以更新数组时需要两个for循环。 一维背包为了优化空间，可以用一维数组，然后从后往前填。二维背包为了优化空间，可以用二维数组，也从后往前填。 假设dp[i][j]表示在i个’0’和j个’1’的限制下，最多能取出的字符串（商品）数，则二维背包代码如下： [cpp] class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 0; i < strs.size(); ++i) { vector<int> cnts(2, 0); for (int j = 0; j < strs[i].size(); ++j)++cnts[strs[i][j] – ‘0’]; for (int j = m; j >= cnts[0]; –j) { for (int k = n; k >= cnts[1]; –k) { dp[j][k] = max(dp[j][k], dp[j – cnts[0]][k – cnts[1]] + 1); } } } return dp[m][n]; } }; [/cpp] 本代码提交AC，用时66MS。]]>