|
2 | 2 |
|
3 | 3 | publicclass_474 { |
4 | 4 | publicstaticclassSolution1 { |
| 5 | +/** |
| 6 | + * credit: https://leetcode.com/problems/ones-and-zeroes/discuss/95811/Java-Iterative-DP-Solution-O(mn)-Space and |
| 7 | + * https://leetcode.com/problems/ones-and-zeroes/discuss/95811/Java-Iterative-DP-Solution-O(mn)-Space/100352 |
| 8 | + * <p> |
| 9 | + * The problem can be interpreted as: |
| 10 | + * What's the max number of str can we pick from strs with limitation of m "0"s and n "1"s. |
| 11 | + * |
| 12 | + * Thus we can define dp[i][j] as it stands for max number of str can we pick from strs with limitation of i "0"s and j "1"s. |
| 13 | + * |
| 14 | + * For each str, assume it has a "0"s and b "1"s, we update the dp array iteratively |
| 15 | + * and set dp[i][j] = Math.max(dp[i][j], dp[i - a][j - b] + 1). |
| 16 | + * So at the end, dp[m][n] is the answer. |
| 17 | + */ |
5 | 18 | publicintfindMaxForm(String[]strs,intm,intn) { |
6 | 19 | int[][]dp =newint[m +1][n +1]; |
7 | 20 | for (Stringstr :strs) { |
|