# Ones and Zeroes

<https://leetcode.com/problems/ones-and-zeroes/description/>

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

## Thoughts

看到按序挑选并且每件物品最多只挑一次以求填满自然想到背包。与传统背包不同的是这里有两件物品要挑，于是用到三维数组。而且它要返回的是能填满的可能个数，不只是否能填满，因此还需要记录个数。让f\[i]\[j]\[k]表示前i个数能填满j个0和k个1的最长长度。

## Code

```
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] f = new int[len + 1][m + 1][n + 1];
        int[][] s = new int[strs.length + 1][2];
        for (int i = 0; i < len; i++) {
            int sum0 = 0;
            int sum1 = 0;
            for (int j = 0; j < strs[i].length(); j++) {
                if (strs[i].charAt(j) == '0') {
                    sum0++;
                } else {
                    sum1++;
                }
            }
            s[i + 1][0] = sum0;
            s[i + 1][1] = sum1;
        }

        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    f[i][j][k] = f[i - 1][j][k];
                    if (j >= s[i][0] && k >= s[i][1]) {
                        f[i][j][k] = Math.max(f[i - 1][j][k], f[i - 1][j - s[i][0]][k - s[i][1]] + 1); 
                    }
                    //System.out.println(i + ", " + j +  ", " + k + ": " + f[i][j][k]);
                }
            }
        }

        return f[len][m][n];
    }
}
```

## Analysis

Errors:

1. j和k的初始值要从0开始。不能从s\[i]\[0]和s\[i]\[1]开始。因为记录的不是当前是否能填满，而是能填满的最长长度，即使当前str不能用于填满，它的长度也至少是f\[i-1]\[j]\[k]. 同样不能从1开始，因为像\[0]\[1]这样很重要的情况没有考虑，不像二维只要考虑\[0]就可以了。

三重循环，时间复杂度是O(lmn).

## Ver.2

```
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] f = new int[m + 1][n + 1];

        for (String str : strs) {
            int zs = 0, os = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '0') {
                    zs++;
                } else {
                    os++;
                }
            }
            for (int i = m; i >= zs; i--) {
                for (int j = n; j >= os; j--) {
                    f[i][j] = Math.max(f[i][j], f[i - zs][j - os] + 1);
                }
            }
        }

        return f[m][n];
    }
}
```