工信部网站备案规定,厦门在线制作网站,琪歌 wordpress,大理如何做百度的网站目录 前言#xff1a; 474. 一和零 - 力扣#xff08;LeetCode#xff09;
总结: 前言#xff1a; 今天我们依旧暴打动态规划 474. 一和零 - 力扣#xff08;LeetCode#xff09;
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集…
目录 前言 474. 一和零 - 力扣LeetCode
总结: 前言 今天我们依旧暴打动态规划 474. 一和零 - 力扣LeetCode
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素集合 x 是集合 y 的 子集 。 其实这也是一个背包问题只不过以前我们的限制条件只有一个重量现在变成了两个一个是m一个是n。那么我们就可以抽象的看他为一个二维的01背包问题。
那么我们就按照动态规划五部曲走
1.确定dp数组的含义及其下标方式dp[i][j] 表示装满 i 个0 和 j 个1 的背包中的最大子集长度
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint (n 1, 0)); for (string str : strs) { int one 0, zero 0;for (char c : str) {if (c 0) zero;else one;}for (int i m; i zero; i--){ for (int j n; j one; j--) {dp[i][j] max(dp[i][j], dp[i - zero][j - one] 1);}}}return dp[m][n];}};
总结: 动态规划很难一眼看出来就是背包问题要仔细甄别
如果我的内容对你有帮助请点赞评论收藏。创作不易大家的支持就是我坚持下去的动力
