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

动态规划14:一和零

动态规划14:一和零

在这里插入图片描述

题目

474. 一和零

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

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

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

示例 1:

输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出:4
解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。

示例 2:

输入:strs = ["10", "0", "1"], m = 1, n = 1
输出:2
解释:最大的子集是 {"0", "1"} ,所以答案是 2 。

提示:

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由 '0''1' 组成
  • 1 <= m, n <= 100

解题思路-五部曲

首先我们先把题型给确定了,这不是多重背包,实质还是01背包

多重背包是每个物品,数量不同的情况。

本题中strs 数组里的元素就是物品,每个物品都是一个!

而m 和 n相当于是一个背包,两个维度的背包

理解成多重背包的同学主要是把m和n混淆为物品了,感觉这是不同数量的物品,所以以为是多重背包。

但本题其实是01背包问题!

只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。

  1. 确定dp数组含义:dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

  2. 确定递推公式:dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

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

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

    然后我们在遍历的过程中,取dp[i][j]的最大值。

    所以递推公式:dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

    此时大家可以回想一下01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。

    这就是一个典型的01背包! 只不过物品的重量有了两个维度而已。

  3. dp数组初始化:因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。

  4. 确定遍历顺序:先物后包,包要倒序,两种维度的顺序不用在意

  5. debug:打印dp数组

代码示例

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m + 1][n + 1];dp[0][0] = 0;//通过给的答案,是不考虑空集的for(String str : strs) {char[] cArr = str.toCharArray();int m0 = 0;//本字符串的0的数量int n1 = 0;//本字符串的1的数量for(char c : cArr) {if(c == '0') m0++;else n1++;}for(int i = m; i >= m0; i--) {for(int j = n; j >= n1; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - m0][j - n1] + 1);}}}return dp[m][n];}
}
  • 时间复杂度: O(kmn),k 为strs的长度
  • 空间复杂度: O(mn)

总结

不少同学刷过这道题,可能没有总结这究竟是什么背包。

此时我们讲解了0-1背包的多种应用,

  • 纯 0 - 1 背包是求 给定背包容量 装满背包 的最大价值是多少。
  • 416. 分割等和子集 是求 给定背包容量,能不能装满这个背包。
  • 1049. 最后一块石头的重量 II 是求 给定背包容量,尽可能装,最多能装多少
  • 494. 目标和是求 给定背包容量,装满背包有多少种方法。
  • 本题是求 给定背包容量,装满背包最多有多少个物品。

这些都是 0-1背包不同维度上的应用,大家可以细心体会!

相关文章:

动态规划14:一和零

动态规划14&#xff1a;一和零 题目 474. 一和零 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度&#xff0c;该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素&#xff0c;集合 x 是集合 y 的 子集 。 …...

C#WPF嵌入字体实例

本文介绍C#WPF嵌入字体实例。 首先创建项目 添加Resources文件夹,添加字体文件,字体文件属性:生成操作为Resources,复制到输出目录:不复制 字体的使用可以采用以下两种方法: 方式一 直接引用 FontFamily="./Resources/#幼圆" 方式二 定义资源 <Applica…...

Linux——Linux权限

Linux权限 前言一、shell命令以及运行原理二、Linux权限的概念Linux权限管理文件访问者的分类&#xff08;人&#xff09;文件类型和访问权限&#xff08;事物属性&#xff09;文件权限值的表示方法文件访问权限的相关设置方法 file指令目录的权限粘滞位 总结 前言 linux的学习…...

android中gradle的kotlin编译配置选项

一、编译配置 1、Android中的配置 使用如下方式开启在Android中的gradle的kotlin编译配置&#xff1a; 该配置在其余平台不可用 android {...compileOptions {sourceCompatibility JavaVersion.VERSION_17targetCompatibility JavaVersion.VERSION_17}kotlinOptions {jvmTar…...

【知识串联】概率论中的值和量(随机变量/数字特征/参数估计)【考研向】【按概率论学习章节总结】(最大似然估计量和最大似然估计值的区别)

就我的概率论学习经验来看&#xff0c;这两个概念极易混淆&#xff0c;并且极为重点&#xff0c;然而&#xff0c;在概率论的前几章学习中&#xff0c;如果只是计算&#xff0c;对这方面的辨析不清并没有问题。然而&#xff0c;到了后面的参数估计部分&#xff0c;却可能出现问…...

NOIP2023模拟6联测27 点餐

题目大意 有 n n n样菜品&#xff0c;每样菜品都有两个权值 a i a_i ai​和 b i b_i bi​&#xff0c;如果你选择了 k k k个菜品&#xff0c;分别为 p 1 , … , p k p_1,\dots,p_k p1​,…,pk​&#xff0c;则你的花费为 ∑ i 1 k a p i max ⁡ i 1 k b p i \sum\limits_{i…...

AMEYA360:类比半导体重磅发布车规级智能高边驱动HD7xxxQ系列

致力于提供高品质芯片的国内优秀模拟及数模混合芯片设计商上海类比半导体技术有限公司(下称“类比半导体”或“类比”)宣布推出重磅新品车规级智能高边驱动HD7xxxQ系列。该系列产品包括车规级单通道高边驱动HD70xxQ和车规级双通道智能高边驱动HD70xx2Q&#xff0c;提供不同通道…...

【HarmonyOS】鸿蒙操作系统架构

HarmonyOS架构 一. 鸿蒙系统定位二. 架构整体遵从分层设计三. HarmonyOS具有的技术特性四. HarmonyOS有三大特征 其它相关推荐&#xff1a; 软考系统架构之案例篇(架构设计相关概念) 系统架构之微服务架构 系统架构设计之微内核架构 所属专栏&#xff1a;系统架构设计师 一. 鸿…...

JSON数据

一、JSON介绍 Android应用程序界面上的数据信息大部分都是通过网络请求从服务器上获取到的&#xff0c;获取到的数据类型常见的就是JSON。JSON是一种新的数据格式&#xff0c;这种格式的数据不可以直接显示到程序的界面上&#xff0c;需要将该数据解析为一个集合或对象的形式才…...

金融领域:怎么保持电力系统连续供应?

银行作为金融领域的关键机构&#xff0c;依赖于高度可靠的电力供应&#xff0c;以保持银行操作的连续性。在电力中断或电力质量问题的情况下&#xff0c;银行可能面临严重的风险&#xff0c;包括数据丢失、交易中断和客户满意度下降。 UPS监控系统在这一背景下变得至关重要&…...

批量重命名文件夹:用数字随机重命名法管理您的文件夹

在文件管理中&#xff0c;文件夹的命名是一项至关重要的任务。一个好的文件夹命名方案可以帮助我们更高效地组织和查找文件。然而&#xff0c;随着时间的推移&#xff0c;我们可能会遇到文件夹数量过多&#xff0c;难以管理和查找的问题。为了解决这个问题&#xff0c;我们可以…...

RPC与HTTP的关系

首选理清楚关系 RPC与HTTP是两个不同维度的东西 HTTP 协议&#xff08;Hyper Text Transfer Protocol&#xff09;&#xff0c;又叫做超文本传输协议&#xff0c;是一种传输协议&#xff0c;平时通过浏览器浏览网页网页&#xff0c;用到的就是 HTTP 协议。 而 RPC&#xff0…...

OpenCV #以图搜图:感知哈希算法(Perceptual hash algorithm)的原理与实验

1. 介绍 感知哈希算法&#xff08;Perceptual Hash Algorithm&#xff0c;简称pHash&#xff09; 是哈希算法的一种&#xff0c;主要用来做相似图片的搜索工作。 2. 原理 感知哈希算法&#xff08;pHash&#xff09;首先将原图像缩小成一个固定大小的像素图像&#xff0c;然后…...

Android多张图片rotation旋转角度叠加/重叠堆放

Android多张图片rotation旋转角度叠加/重叠堆放 <?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"http://schemas.android.com/apk/res-auto"…...

HBuilderX 自定义语法提示

在开发实践中&#xff0c;会使用到各种第三方组件&#xff0c;比如Element UI&#xff0c;通常的做法是到官网中复制模板再在本地根据设计要求进行修改&#xff0c;或是从其它已经实现的组件中复制相似的内容。但每次复制粘贴确实比较麻烦。 在HBuilderx中可以设置代码块来创建…...

Leetcode—2562.找出数组的串联值【简单】

2023每日刷题&#xff08;十四&#xff09; Leetcode—2562.找出数组的串联值 实现代码 long long findTheArrayConcVal(int* nums, int numsSize){int left 0;int right numsSize - 1;long long sum 0;while(left < right) {if(left right) {sum nums[left];break;}…...

T0外部计数输入

/*----------------------------------------------- 内容&#xff1a;通过外部按键计数进入中断执行LED取反 ------------------------------------------------*/ #include<reg52.h> //包含头文件&#xff0c;一般情况不需要改动&#xff0c;头文件包含特殊功能寄存器的…...

分治法求解棋盘覆盖问题

分治法求解棋盘覆盖问题 如何应用分治法求解棋盘覆盖问题呢&#xff1f;分治的技巧在于如何划分棋盘&#xff0c;使划分后的子棋盘的大小相同&#xff0c;并且每个子棋盘均包含一个特殊方格&#xff0c;从而将原问题分解为规模较小的棋盘覆盖问题。 基本思路 棋盘覆盖问题是…...

爱写bug的小邓程序员个人博客

博客网址: http://www.006969.xyz 欢迎来到我的个人博客&#xff0c;这里主要分享我对于前后端相关技术的学习笔记、项目实战经验以及一些技术感悟。 在我的博客中&#xff0c;你将看到以下主要内容&#xff1a; 技术文章 我将会分享我在学习前后端技术过程中的一些感悟&am…...

selenium判断元素可点击、可见、可选

1、判断元素是否可以点击 判断元素是否可以点击&#xff0c;WebElement对象调用is_enabled() is_enabled()方法返回一个布尔值&#xff0c;若可点击返回&#xff1a;True。若不可点击则返回&#xff1a;False from selenium import webdriver import time from selenium.web…...

Stable Yogi Leather-Dress-Collection实战:SpringBoot微服务集成与API开发

Stable Yogi Leather-Dress-Collection实战&#xff1a;SpringBoot微服务集成与API开发 最近在帮一个做时尚电商的朋友做技术方案&#xff0c;他们想在自己的商品详情页里&#xff0c;根据用户上传的真人照片&#xff0c;实时生成虚拟试穿效果。核心需求很明确&#xff1a;需要…...

零基础玩转像素幻梦:快速生成《光纹苔藓姑苏幻梦》同款像素画

零基础玩转像素幻梦&#xff1a;快速生成《光纹苔藓姑苏幻梦》同款像素画 1. 像素幻梦初体验 1.1 什么是像素幻梦创意工坊 像素幻梦创意工坊&#xff08;Pixel Dream Workshop&#xff09;是一款基于FLUX.1-dev扩散模型构建的AI像素艺术生成工具。它采用明亮的16-bit像素风格…...

Youtu-Parsing快速部署指南:一键启动Web服务,开箱即用解析工具

Youtu-Parsing快速部署指南&#xff1a;一键启动Web服务&#xff0c;开箱即用解析工具 1. 项目概述与核心价值 Youtu-Parsing是腾讯优图实验室推出的多模态文档智能解析模型&#xff0c;基于Youtu-LLM-2B构建&#xff0c;专为解决复杂文档解析难题而设计。不同于传统OCR工具&…...

Noi:整合多 AI 服务的新利器能否突出重围?

Noi&#xff1a;一站式 AI 服务整合新体验Noi 是一款图形用户界面&#xff08;GUI&#xff09;应用程序&#xff0c;它的核心亮点在于将所有 AI 服务整合到一处。用户通过单一用户界面&#xff08;UI&#xff09;就能访问 ChatGPT、Claude、Gemini、Perplexity 等多个服务&…...

Java面试题精讲:Qwen-Image-Edit-F2P集成开发常见问题

Java面试题精讲&#xff1a;Qwen-Image-Edit-F2P集成开发常见问题 1. 引言 最近在Java技术面试中&#xff0c;我发现很多候选人在AI模型集成方面存在不少困惑。特别是像Qwen-Image-Edit-F2P这样的人脸驱动图像生成模型&#xff0c;虽然功能强大&#xff0c;但在实际Java项目集…...

Java毕业设计基于springboot+vue的旧时光咖啡厅管理系统

前言 该系统旨在提高咖啡厅的运营效率和服务质量&#xff0c;通过集成订单管理、库存管理、员工管理、客户管理等多个功能模块&#xff0c;实现对咖啡厅日常运营的全面管理。同时&#xff0c;系统还提供了丰富的数据分析和报表功能&#xff0c;帮助管理者更好地了解咖啡厅的运营…...

矩阵LED与矩阵按键的扫描驱动原理及实现

1. 矩阵LED与矩阵按键的硬件结构解析 第一次接触矩阵LED和矩阵按键时&#xff0c;我完全被那些交叉的线路搞晕了。后来才发现&#xff0c;它们的本质就是行和列的交叉网络。想象一下围棋棋盘&#xff0c;横线是行&#xff0c;竖线是列&#xff0c;每个交叉点就是一颗棋子——在…...

3种文档转换难题的解决方案:Cloud Document Converter工具深度解析

3种文档转换难题的解决方案&#xff1a;Cloud Document Converter工具深度解析 【免费下载链接】cloud-document-converter Convert Lark Doc to Markdown 项目地址: https://gitcode.com/gh_mirrors/cl/cloud-document-converter 核心价值&#xff1a;文档格式转换的效…...

基于模型参考的滑模控制/MRSMC 基于模型参考的滑模控制(MRSMC, Model Refe...

基于模型参考的滑模控制/MRSMC 基于模型参考的滑模控制&#xff08;MRSMC, Model Reference Sliding Mode Control&#xff09;是一种结合了模型参考控制和滑模控制优点的控制策略。 它通常用于系统的鲁棒控制&#xff0c;尤其是在面对模型不确定性和外部扰动时。 在simulink中…...

别再只用箱线图了!用Python的PtitPrince库5分钟搞定雨云图,数据分布一目了然

数据可视化新选择&#xff1a;用PtitPrince打造专业级雨云图 在数据分析的世界里&#xff0c;可视化工具的选择往往决定了我们能否准确传达数据背后的故事。传统箱线图虽然简洁&#xff0c;却隐藏了太多细节&#xff1b;提琴图展示了分布形态&#xff0c;却丢失了原始数据点。这…...