[数据结构与算法]474. 一和零

思路

首先，这个题是有两个容量的背包问题。分别是容量为m，和容量为n的背包。这点是和其他题目不同的地方。

运用动态规划五部曲。

1.确定dp数组

dp[i][j]表示有i个0和j个1的背包中，所装的字符串的个数。

2.递推公式

dp[i][j] = Math.max(dp[i][j],dp[i-zeroNumber][j-oneNumber]+1);

此处的+1是因为，如果当前字符串放入背包则背包中字符串的个数将会+1；

3.dp数组初始化

根据dp数组的定义就可以知道dp[0][0]=0

4.确定遍历顺序

可以根据递推公式知道，dp[i][j]与其前面的元素有关，所以应该是前序遍历，但是背包容量应该后序遍历，防止物品的重复放入。又因为本题的i和j都是背包容量，所以都是后序遍历。

5.打印dp数组

数组的最后一个元素就是最后的结果。

代码

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int dp[][] = new int[m+1][n+1];
        dp[0][0] = 0;
        for(String str:strs){
            int zeroNumber = 0;
            int oneNumber = 0;
            for(char c:str.toCharArray()){
                if(c=='0'){
                    zeroNumber++;
                }
                if(c=='1'){
                    oneNumber++;
                }
            }
            for(int i = m;i>=zeroNumber;i--){
                for(int j = n;j>=oneNumber;j--){
                    dp[i][j] = Math.max(dp[i][j],dp[i-zeroNumber][j-oneNumber]+1);
                }
            }
        }
        return dp[m][n];
    }
}