# Leetcode 474 - Ones and zeroes

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0’s and n 1’s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Example:

Note:

• This is a 01 knapsack problem.
• Just like optimizing 2D dp array to 1D. This should be a 3D dp array if we do it in a traditional way, but we can simplify the space! Imagine it was dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeroes][k-ones] + 1), we can simplify it as dp[j][k] = max(dp[j][k], dp[j-zeroes][k-ones] + 1).
• Please remember to iterate j and k in reversed order just like what we did in other DP problems.