当前位置: 首页 > 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…...

Acode:重新定义Android移动代码编辑体验

Acode&#xff1a;重新定义Android移动代码编辑体验 【免费下载链接】Acode Acode - powerful text/code editor for android 项目地址: https://gitcode.com/gh_mirrors/ac/Acode 在移动开发日益普及的今天&#xff0c;拥有一款高效的移动代码编辑器成为开发者的迫切需…...

Zotero插件安装失败?手把手教你解决版本兼容问题(以better-notes为例)

Zotero插件安装失败&#xff1f;手把手教你解决版本兼容问题&#xff08;以better-notes为例&#xff09; 学术研究离不开文献管理工具&#xff0c;Zotero作为开源免费的文献管理神器&#xff0c;凭借其强大的功能和丰富的插件生态&#xff0c;成为众多科研工作者的首选。然而…...

深入剖析Dynamic-Datasource:迭代器模式在数据源扩展中的完整实现指南

深入剖析Dynamic-Datasource&#xff1a;迭代器模式在数据源扩展中的完整实现指南 【免费下载链接】dynamic-datasource dynamic datasource for springboot 多数据源 动态数据源 主从分离 读写分离 分布式事务 项目地址: https://gitcode.com/gh_mirrors/dy/dynamic-dataso…...

Python内存暴涨突然崩溃?3个被90%开发者忽略的GC调优关键点揭秘

第一章&#xff1a;Python内存暴涨与崩溃的典型现象诊断当Python程序在运行中突然响应迟缓、频繁触发MemoryError&#xff0c;或进程被操作系统强制终止&#xff08;如Linux下收到SIGKILL (9)&#xff09;&#xff0c;往往标志着内存使用已严重失控。这类问题通常不会立即暴露&…...

从逆向工程到实战:深度解析钉钉本地数据取证与加密对抗

1. 钉钉本地数据存储结构解析 第一次拆解钉钉的数据库文件时&#xff0c;我对着那堆加密的.sqlite文件发了半小时呆。作为国内用户量最大的企业通讯工具&#xff0c;钉钉在数据保护上确实下了狠功夫。Android和iOS两个平台的数据存储方式既有共性又存在微妙差异&#xff0c;这正…...

腾讯音乐开源的SuperSonic到底强在哪?手把手教你配置专属数据分析Agent

腾讯音乐SuperSonic深度解析&#xff1a;如何打造智能数据问答Agent 当企业数据量呈指数级增长时&#xff0c;传统BI工具已经难以满足实时决策的需求。腾讯音乐开源的SuperSonic作为新一代AIBI平台&#xff0c;通过融合Chat BI与Headless BI两大范式&#xff0c;正在重新定义数…...

ollama-QwQ-32B流式响应:优化OpenClaw长任务等待体验

ollama-QwQ-32B流式响应&#xff1a;优化OpenClaw长任务等待体验 1. 为什么需要流式响应&#xff1f; 去年冬天&#xff0c;我尝试用OpenClaw自动整理一整年的会议录音转文字稿。当我把包含200多小时音频的文件夹丢给AI处理时&#xff0c;终端突然卡在了"正在处理第1个文…...

从零开始优化接口性能:QPS、TPS、OTPS、TP99的实战指南

从零开始优化接口性能&#xff1a;QPS、TPS、OTPS、TP99的实战指南 当你的电商系统在秒杀活动中突然崩溃&#xff0c;或是聊天机器人回复速度慢到用户流失时&#xff0c;性能指标就不再是枯燥的数字&#xff0c;而是决定业务存亡的关键。我曾经历过一次惨痛的教训&#xff1a;某…...

告别地图切换卡顿:优化OpenLayers加载天地图瓦片的性能与体验指南

告别地图切换卡顿&#xff1a;优化OpenLayers加载天地图瓦片的性能与体验指南 在WebGIS项目开发中&#xff0c;地图加载速度和操作流畅度直接影响用户体验。当项目上线后&#xff0c;用户反馈地图切换卡顿、加载缓慢时&#xff0c;开发者往往需要深入底层优化才能解决问题。本文…...

Auto-Photoshop-StableDiffusion-Plugin:在Photoshop中无缝集成AI图像生成的技术实现方案

Auto-Photoshop-StableDiffusion-Plugin&#xff1a;在Photoshop中无缝集成AI图像生成的技术实现方案 【免费下载链接】Auto-Photoshop-StableDiffusion-Plugin A user-friendly plug-in that makes it easy to generate stable diffusion images inside Photoshop using eithe…...