题目描述：

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:

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".
```

解题思路：

```for s in strs:
zero, one = s.count('0'), s.count('1')
for x in range(m, zero - 1, -1):
for y in range(n, one - 1, -1):
dp[x][y] = max(dp[x - zero][y - one] + 1, dp[x][y])```

Python代码：

``````class Solution(object):
def findMaxForm(self, strs, m, n):
"""
:type strs: List[str]
:type m: int
:type n: int
:rtype: int
"""
dp = [[0] * (n + 1) for x in range(m + 1)]
for s in strs:
zero, one = s.count('0'), s.count('1')
for x in range(m, zero - 1, -1):
for y in range(n, one - 1, -1):
dp[x][y] = max(dp[x - zero][y - one] + 1, dp[x][y])
return dp[m][n]
``````

Java代码：

``````public class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int dp[][] = new int[m + 1][n + 1];
int ans = dp[0][0] = 0;
for (String s : strs) {
int zero = 0, one = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '0') {
zero++;
} else {
one++;
}
}
for (int i = m; i > zero - 1; i--) {
for (int j = n; j > one - 1; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
}
}
}
return dp[m][n];
}
}
``````

Pingbacks已关闭。

1. 赤壁的火神 发布于 2016年12月12日 13:51 #

问一下x和y的循环为什么要倒序呢 我就是正序写的
if i + zeros <= m and j + ones <= n: dp[i + zeros][j + ones] = max(dp[i][j] + 1, dp[i + zeros][j + ones])
然后发现是错的。。。比赛的时候卡在这里一直过不去。。。现在都没懂。。。

2. 在线疯狂 发布于 2016年12月13日 12:11 #

将dp数组扩展一维，状态转移方程：dp[k][i+zero][j+one] = max(dp[k][i+zero][j+one], dp[k-1][i][j] + 1)，这样就可以正序遍历了。
若dp数组是两维，正序遍历会存在同一个目标串被使用多次的情况。