您的位置:首页 > 新闻 > 热点要闻 > 动态规划---一和零

动态规划---一和零

2025/1/8 0:38:22 来源:https://blog.csdn.net/m0_65096633/article/details/141925302  浏览:    关键词:动态规划---一和零

题目:

给你一个二进制字符串数组 strs 和两个整数 mn

请你找出并返回 strs 的最大子集的长度,该子集中 最多m0n1

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y子集

思路:

动态规划五部曲:

1.确定dp数组及含义

dp数组需要有两个维度,i来遍历数字0,j来遍历数字1。dp[i][j]表示最多有i个数字0,j个数字1时最大子集的长度。

2.确定递推公式

dp[i][j]可以由前一个str里的字符串推导出来,str里的字符串有zeroNum个0,oneNum个1

dp[i][j]就可以是dp[i-zeroNum][j-oneNum]+1

在遍历过程中取最大值,所以递推公式为dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)

3.dp数组初始化

全初始化为0即可。

4.确定遍历顺序

外层for正序循环遍历物品(字符串),内层for循环倒序遍历背包容量(m和n)。

5.举例推导dp数组

strs = ["10", "0001", "111001", "1", "0"], m = 3, n = 3

dp[i][j]=[[0,1,1,1],

             [1,2,2,2],

             [1,2,3,3],

             [1,2,3,3]]

代码:

    public int findMaxForm(String[] strs, int m, int n) {int[][] dp=new int[m+1][n+1];int zeroNum,oneNum;for(String s:strs){oneNum=0;zeroNum=0;for(char c:s.toCharArray()){if(c=='0')zeroNum++;elseoneNum++;}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];}

版权声明:

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

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