动态规划— 一和零
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个1
for(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)
原文地址：https://blog.csdn.net/xiao_jin_gang/article/details/143494936
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！