Leetcode 474. Ones and Zeroes

[Woodyiiiiiii]

这道题的DP解法跟416. Partition Equal Subset Sum一样。

题目条件都是在一个数组中，利用其中的子集或者每次结果集中使用一次。

或者说，这是用DP解决subset问题的通式。

将题目所求值作为长度建立DP数组，递推公式解法模版如下：

for (int i = 0; i < nums.length; ++i) {   // 循环题目所给数组
    for ()          // 从大到小(或从右往左)的顺序循环DP数组(长度一般是target)
}

所以此题代码是：

class Solution {
    
    public int findMaxForm(String[] strs, int m, int n) {
        
        int[][] dp = new int[m + 1][n + 1];
        
        for (String str : strs) {
            int ones = 0;
            int zeroes = 0;
            for (int i = 0; i < str.length(); ++i) {
                if (str.charAt(i) == '1') {
                    ones++;
                } else if (str.charAt(i) == '0') {
                    zeroes++;
                }
            }
            
            for (int i = m; i >= zeroes; --i) {
                for (int j = n; j >= ones; --j) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroes][j - ones] + 1);
                }
            }
        }
        
        return dp[m][n];
        
    }
}

---

参考资料：

• https://leetcode.com/problems/ones-and-zeroes/