当前位置: 首页 > news >正文

力扣474-一和零(Java详细题解)

题目链接:474. 一和零 - 力扣(LeetCode)

前情提要:

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

最近刚学完01背包,所以现在的题解都是以01背包问题为基础再来写的。

如果大家不懂01背包的话,建议可以去学一学,01背包问题可以说是背包问题的基础。

如果大家感兴趣,我后期可以出一篇专门讲解01背包问题。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组 利于debug。

每一个dp题目如果都用这五步分析清楚,那么这道题就能解出来了。

题目思路:

本题要求的是m个0n个1时子集中的最大长度。

其实这m个0n个1就是一种容器,我们要将该容器装满,求得子集的最大长度即可。

那么可以将这种容器抽象为背包,只不过这个背包是二维的,最大容量为m个0,n个1。

那么问题可以转化为将这个背包装满,求物品的数量。

接下来我们用动规五部曲来系统分析一下。

1.确定dp数组和i下标的含义。

我们这个背包是二维的,所以我们的dp数组也得是二维的。

dp[i] [j]指有i个0m个1时最大能装的物品数量。

2.确定递推公式。

首先我们来看看纯01背包问题的递推公式。

dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);

那么本题的递推公式其实和01背包递推公式相似。

每个物品只有选和不选俩种状态。

不选的话就是dp[i] [j]因为没有选该物品,所以背包容量不变。

选的话就是dp[i - x] [j - y] + 1;其实x表示的是当前物品0的数量,y表示当前物品1的数量。

因为选的话,就得求出加入当前物品之前的背包容量能装入的最大物品数量,再加上该物品。也就是 + 1;

所以我们的递推公式就是 dp[i] [j] = Math.max(dp[i] [j],dp [i - x] [j - y] + 1);

3.dp初始化。

dp[0] [0]指的就是当背包中有0个0和0个1时能装入的物品数量,所以dp[0] [0] = 0;

其他的非0下标可以通过dp数组推出来,所以其他的我们就不初始化,没有意义。

4.确定dp的遍历顺序。

该题与01背包的遍历顺序相同,物品从前往后遍历,背包容量从后往前遍历上为了保证每个物品只放入了一次。

5.如果没有ac打印dp数组 利于debug。

如果没有出现差错,我们就可以不用打印,因为我是写题解,所以我就不添加核心代码以外的代码,不然代码显的有些冗余。

举个例子。

在这里插入图片描述

最终代码:

class Solution {public int findMaxForm(String[] strs, int m, int n) {// 本题核心思路就是把这个背包装满,最多能装多少物品。//同时本题背包具有俩个维度。//递推公式 dp[i][j]是指在i个0j个1下能装满的物品数量。//那么每个物品也只有选和不选,该物品不选就是dp[i][j]//选的话就是dp[i - x][j - y] + 1,选择该物品的话要将装入前能装的最多物品加1,也就是加上这个物品//本题是把每个子集当做一个物品//确定dp数组int dp[][] = new int[m + 1][n + 1];//初始化dp数组dp[0][0] = 0;//遍历物品for (String s : strs) {int x = 0, y = 0;//统计每个物品的01数量for (int v = 0;v < s.length();v ++) {if (s.charAt(v) == '0') {x++;} else {y++;}}//遍历背包//由于背包是俩个维度所以俩个要从后往前遍历 确保物品只放入了一次for (int i = m; i >= x; i--) {for (int j = n; j >= y; j--) {//递推公式dp[i][j] = Math.max(dp[i][j], dp[i - x][j - y] + 1);}}}return dp[m][n];}
}

这一篇博客就到这了,如果你有什么疑问和想法可以打在评论区,或者私信我。

我很乐意为你解答。那么我们下篇再见!

http://www.lryc.cn/news/434505.html

相关文章:

  • 【话题】量子计算:前沿技术与应用前景深度解析
  • 第11章 32位x86处理器编程架构
  • 加密软件是什么?有哪些用处呢?
  • 浅谈C#之任务调度TaskScheduler
  • SQL server 日常运维命令
  • 基于协同过滤算法+SpringBoot+Vue+MySQL的商品推荐系统
  • VSCode中latex文件(Misplaced alignment tab character .LaTeX
  • 如何给电脑设置静态IP地址:详细步骤与指南
  • 【Mysql】系统服务启动访问报错问题处理:this is incompatible with sql_mode=only_full_group_by
  • 安装oh-my-zsh后报错zsh: command not found: conda问题解决
  • 避免 PyCharm 将该 Python 脚本作为测试运行
  • 【Sqlite】.NET Framework使用Sqlite的注意事项
  • 2024下《系统集成项目管理工程师》50个高频考点汇总!值得收藏
  • Java 远程调用接口(RMI)
  • torch.squeeze()
  • COD论文笔记 BiRefNet
  • 表单项标签简单学习
  • 固态硬盘和机械硬盘区别?固态硬盘和机械硬盘哪个好?
  • QQ频道机器人零基础开发详解(基于QQ官方机器人文档)[第三期]
  • 亚信安全全球云安全SaaS运营总部落地厦门 安全点亮一带一路
  • 在cmd中输入mysql无法运行(环境变量配置保姆级教程)
  • 在Webmin上默认状态无法正常显示 Mariadb V11.02及以上版本
  • C和指针:预处理(#include/define/if...)
  • 【Java数据结构】泛型的进阶部分(泛型通配符)
  • 大模型实战一、Ollama+RagFlow 部署本地知识库
  • 系统工程建模MBSE
  • SVN的使用技巧
  • 使用 RabbitMQ 实现秒杀订单系统的异步消息处理
  • oracle19.3单机升级到Oracle19.22
  • 半导体的发展--创世新产品介绍