您的位置:首页 > 科技 > IT业 > 好订单网服装外发加工_产品设计师网站_百度搜索排名优化哪家好_电脑培训学校排名

好订单网服装外发加工_产品设计师网站_百度搜索排名优化哪家好_电脑培训学校排名

2024/12/23 5:41:23 来源:https://blog.csdn.net/xiao_jin_gang/article/details/143494936  浏览:    关键词:好订单网服装外发加工_产品设计师网站_百度搜索排名优化哪家好_电脑培训学校排名
好订单网服装外发加工_产品设计师网站_百度搜索排名优化哪家好_电脑培训学校排名

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)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com