---
# System prepended metadata

title: 0474. Ones and Zeroes
tags: [Leetcode, Dynamic Programming, Knapsack Problem, Medium]

---

# 0474. Ones and Zeroes
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Knapsack Problem`
Link: https://leetcode.com/problems/ones-and-zeroes/
## 思路
![](https://i.imgur.com/XAQbVco.png)
虽然也可以理解成0和1的数目最大是c1，c2的时候
但是"恰好是"更容易讨论

## Code
```java=
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int l = strs.length;
        int[][] dp = new int[m+1][n+1];
        
        for(int i=1; i<=l; i++){
            String str = strs[i-1];
            int cnt0 = 0, cnt1 = 0;
            for(int j=0; j<str.length(); j++){
                if(str.charAt(j)=='0') cnt0++;
                else cnt1++;
            }
            for(int j=m; j>=cnt0; j--){
                for(int k=n; k>=cnt1; k--){
                    dp[j][k] = Math.max(dp[j][k], dp[j-cnt0][k-cnt1]+1);
                }
            }
        }
        
        int ans = 0;
        for(int i=0; i<=m; i++){
            for(int j=0; j<=n; j++){
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}
```