class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m+1][n+1];//dp[i][j]表示i个0和j个1时的最大子集int oneNum = 0, zeroNum = 0;for(String str : strs){oneNum = 0;zeroNum = 0;for(char c : str.toCharArray()){if(c == '0'){zeroNum++;}else{oneNum++;}}//dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1for(int i = m; i>= zeroNum; i--){for(int j = n; j>= oneNum; j--){dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
}
确定dp数组以及下标的含义
dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
确定递推公式
递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
dp数组初始化
dp[0] 初始为0
确定遍历顺序
遍历背包的for循环, for循环倒序遍历
复杂度分析
- 时间复杂度: O(kmn),k 为strs的长度
- 空间复杂度: O(mn)