###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 474. Ones and Zeroes

## [題目連結:] https://leetcode.com/problems/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 1:**

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

**Example 2:**

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

## 解題想法:
* 此題為數組中每個字符串皆有一些0與1，若給m個0、n個1
* 從數組中取最多的字符串
* 使其字符串中0與1的出現次數不超過m與n

* 求次數而非具體細節: 使用DP
* 定義dp[i][j]: **表示具有i個0、j個1的最大子集合數**
* 對於strs中每個string，先求出該string的0、1數量
* zero
* one
* 比較對象為: dp[i-zero][j-one]表示當前的i扣掉zero數量、當前的j扣掉one數量，所具有的最大子集合數
* 轉移方程式即為: dp[i][j]=max(dp[i][j], **dp[i-zero][j-one]+1**)
* +1表示加入當前string
* 注意~填入dp時候，需由大到小進行
* for i in range(m,zero-1,-1): **不能低於zero的數量**
* for j in range(n,one-1,-1): **不能低於one的數量**

## Python:

class Solution(object):
    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int for Zero
        :type n: int for One
        :rtype: int
        """
        #dp[i][j]: 最多可有i個0與j個1的 最大子集數 
        dp=[ [0]*(n+1) for _ in range(m+1)]
        
        for str in strs:
            zero=0
            one=0
            for item in str:
                if item=='0':
                    zero+=1
                elif item=='1':
                    one+=1
            #填入dp 從大到小填!!!!
            for i in range(m,zero-1,-1): #不能低於zero的數量
                for j in range(n,one-1,-1): #不能低於one的數量
                    dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1)
        return dp[m][n]

strs = ["10","0001","111001","1","0"]
m = 5
n = 3
result=Solution()
ans=result.findMaxForm(strs,m,n)
print(ans)

## C++:

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1,0));
        for (string item: strs){
            int zero=0,one=0;
            for (char val: item){
                (val=='0')? zero+=1: one+=1;
            }
            //dp
            for (int i=m; i>=zero; i--){
                for (int j=n; j>=one; j--){
                    dp[i][j]=max(dp[i][j], dp[i-zero][j-one]+1);
                }
            }
        }
        return dp[m][n];
    }
};