leetcode 474. Ones and Zeroes

题目链接：

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

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组成，还有m个0和n个1, 要我们求出用给定数目的0和1能最多组合出的给定字符串的数目。

思路

其实我们如果做这道题的话，思路可能如下：

1. 遍历每个字符串，这个字符串要么选，要么不选。
2. 咦，这个思路好像和（0-1）背包有点像呀，那么我们如何类比为0-1背包问题呢。
3. 经典0-1背包问题最主要的两个变量就是value和weight。选择一个字符串，相当于我们背包的value 加了1，因为我们最后求的是字符串的数量；但同时，（假设该字符串中0的数量为mm, n的数量为nn）相当于给背包增加了mm个0的重量和nn个1的重量。
4. 如果套用0-1背包的递归公式，好像这个题目已经解决啦！

递归公式

• 0-1背包递归公式
  
• 套用之后的递归公式
  1. F(i, m, n)表示将前i个物品放入容量为<m, n> 的背包中，其中，m和n分别表示0和1的数量。
  2. 如果不放第i个字符串，此时的总价值为F(i-1, m, n).
  3. 如果放第i个字符串，假设第i个字符串中0的数量为mm, 1的数量为nn，则总价值为1 + F(i-1, m -mm, n - nn);

至此，我们已经得到了递推公式，代码实现了就好，是不是很简单！

代码一

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if(m == 0 && n == 0) return 0;
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        int ans = 0;
        for(int i = 1; i <= strs.length; i++) {
            String curr = strs[i - 1];
            int mm = getNum(curr, '0');
            int nn = getNum(curr, '1');
            for(int j = 0; j <=m; j++) {
                for(int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j - mm >= 0 && k - nn >= 0) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j - mm][k - nn] + 1);
                        if (ans < dp[i][j][k]) ans = dp[i][j][k];
                    }
                }
            }

        }
        return ans;

    }

    private int getNum(String str, char c) {
        int cnt = 0;
        for (Character cc : str.toCharArray()) {
            if(cc == c) cnt++;
        }
        return cnt;
    }
}

代码二

上边的代码使用了三维数组，经过空间优化之后，我们只用二维数组就好了，但是要注意遍历的j和k时要倒着遍历。（和0-1背包的空间优化思路一模一样）

class Solution {
  public int findMaxForm(String[] strs, int m, int n) {
      if(m == 0 && n == 0) return 0;
      int[][] dp = new int[m + 1][n + 1];
      int ans = 0;
      for(int i = 1; i <= strs.length; i++) {
          String curr = strs[i - 1];
          int mm = getNum(curr, '0');
          int nn = getNum(curr, '1');
          for(int j = m; j >= 0; j--) {
              for(int k = n; k >= 0; k--) {
                  if(j - mm >= 0 && k - nn >= 0) {
                      dp[j][k] = Math.max(dp[j][k], dp[j - mm][k - nn] + 1);
                      if (ans < dp[j][k]) ans = dp[j][k];
                  }
              }
          }

      }
      return ans;

  }

  private int getNum(String str, char c) {
      int cnt = 0;
      for (Character cc : str.toCharArray()) {
          if(cc == c) cnt++;
      }
      return cnt;
  }
}