leetcode474

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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.
 

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

已知有m个0和n个1，问最多能构成数组中多少个数字。已知每个0和1只能使用一次。

思路和代码

先是用深度优先遍历的思想进行了实现，结果很明显是超时了。接着采用动态规划的思想，其实这题就是背包问题的一个演化。假设已知道m个0和n个1能够从数组中前i个元素最多拼成多少个元素，则m个0和n个1能够从数组中前i+1个元素能够拼成最多的元素个数有如下两个场景：

  1. 第i+1个字符串的0的个数和1的个数分别小于m和n，则有两种选择，分别是选择该字符串和不选择该字符串，选择该字符串的话，max[i+1][m][n] = 1 + max[i][m-numOfZero(str)][n-numOfOne(str)], 如果不选择的话，max[i+1][m][n] = max[i-1][m][n]。从两个选项中选择一个最大的即可。
  2. 否则的话，max[i+1][m][n] = max[i][m][n]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
   public int findMaxForm2(String[] strs, int m, int n) {
    int[][] dp = new int[m+1][n+1];
    for (String s : strs) {
        int[] count = count(s);
        for (int i=m;i>=count[0];i--) 
            for (int j=n;j>=count[1];j--) 
                dp[i][j] = Math.max(1 + dp[i-count[0]][j-count[1]], dp[i][j]);
    }
    return dp[m][n];
}
    
public int[] count(String str) {
    int[] res = new int[2];
    for (int i=0;i<str.length();i++)
        res[str.charAt(i) - '0']++;
    return res;
 }