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

day-56 代码随想录算法训练营(19)动态规划 part 16

538.两个字符串的删除操作

思路一:
  • 1.dp存储:以word1[i-1]结尾,word2[j-1]结尾,最少进行dp[i][j]次操作
  • 2.动态转移方程: if(word1[i-1]==word2[i-1]) dp[i][j]=dp[i-1][j-1];
  •                 else dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1)
  • 3.初始化:dp[i][0]=i   dp[0][j]=j
  • 4.遍历顺序:1~尾巴
class Solution {
public:int minDistance(string word1, string word2) {int n=word1.size(),m=word2.size();vector<vector<int>>dp(n+1,vector<int>(m+1,0));for(int i=0;i<=n;i++) dp[i][0]=i;//相同时需要删除所有字符串for(int j=0;j<=m;j++) dp[0][j]=j;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];//不需要操作else dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);//两个字符串各自的操作取最小}}return dp[n][m];}
};

72.编辑距离

思路:
  • 1.dp存储:以word1[i]结尾,word2[j]结尾,使两个字符串相同的最小操作次数
  • 2.动态转移方程: if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
  •                 else dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1)
  • 3.初始化:dp[i][0]=i   dp[0][j]=j
  • 4.遍历顺序:1~n 1~m
class Solution {
public:int minDistance(string word1, string word2) {int n=word1.size(),m=word2.size();vector<vector<int>>dp(n+1,vector<int>(m+1,0));for(int i=0;i<=n;i++) dp[i][0]=i;for(int j=0;j<=m;j++) dp[0][j]=j;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//添加和删除都是一样的,两边各添加和删除;改变就是上一次的值+1if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];else dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));}}return dp[n][m];}
};

相关文章:

day-56 代码随想录算法训练营(19)动态规划 part 16

538.两个字符串的删除操作 思路一&#xff1a; 1.dp存储&#xff1a;以word1[i-1]结尾&#xff0c;word2[j-1]结尾&#xff0c;最少进行dp[i][j]次操作2.动态转移方程&#xff1a; if(word1[i-1]word2[i-1]) dp[i][j]dp[i-1][j-1]; else dp[i][j]min(dp[i-1][…...

蓝桥等考Python组别四级005

第一部分:选择题 1、Python L4 (15分) 字符“0”的ASCII码值为48,则字符“5”的ASCII码值为( )。 3953120240正确答案:B 2、Python L4 (15分) 下面哪个是Python中正确的变量名?( ) ABC#sup01Trueif正确答案:B...

【Linux】diff 命令

【Linux】diff 命令——并排格式输出 功能 diff 以逐行的方式&#xff0c;比较文本文件的异同处。 如果指定要比较目录&#xff0c;则 diff 会比较目录中相同文件名的文件&#xff0c;但不会比较其中子目录 diff [参数] [文件A] [文件B]diff [参数] [目录A] [目录B]【参数】…...

【51单片机】9-定时器和计数器

1.定时器的介绍 1.什么是定时器 &#xff08;1&#xff09;SoC的一种内部的外设【在单片机里面&#xff0c;但是在CPU外面】 &#xff08;2&#xff09;定时器就是CPU的”闹钟“ 2.什么是计数器 &#xff08;1&#xff09;定时器就是用计数的原始实现的 &#xff08;2&#xf…...

2023年海南省职业院校技能大赛(高职组)信息安全管理与评估赛项规程

2023年海南省职业院校技能大赛&#xff08;高职组&#xff09; 信息安全管理与评估赛项规程 一、赛项名称 赛项名称&#xff1a;信息安全管理与评估 英文名称&#xff1a;Information Security Management and Evaluation 赛项组别&#xff1a;高等职业教育 赛项归属产业&…...

大模型深挖数据要素价值:算法、算力之后,存储载体价值凸显

文 | 智能相对论 作者 | 叶远风 18.8万亿美元&#xff0c;这是市场预计2030年AI推动智能经济可产生的价值总和&#xff0c;其中大模型带来的AI能力质变无疑成为重要的推动力量。 大模型浪潮下&#xff0c;业界对AI发展的三驾马车——算力、算法、数据任何一个维度的关注都到…...

AI文章,AI文章生成工具

在互联网时代&#xff0c;随着信息爆炸式增长&#xff0c;文章的需求愈发旺盛。从博客、新闻、社交媒体到企业宣传&#xff0c;文字作为传达信息、吸引受众的工具变得愈发重要。但问题是&#xff0c;对于很多人来说&#xff0c;创作一篇高质量的文章并不容易。时间、创意、写作…...

mac有必要用清理软件吗?有哪些免费的清理工具

当我们谈到Mac电脑时&#xff0c;很多人都会觉得它比Windows系统更加稳定和高效&#xff0c;也更不容易积累垃圾文件。但实际上&#xff0c;任何长时间使用的操作系统都会逐渐积累不必要的文件和缓存。那么&#xff0c;对于Mac用户来说&#xff0c;有必要使用专门的清理软件吗&…...

React 全栈体系(十八)

第九章 React Router 6 二、代码实战 6. 路由的 params 参数 6.1 routes /* src/routes/index.js */ import About from "../pages/About"; import Home from "../pages/Home"; import Message from "../pages/Message"; import News from &q…...

TCP/UDP

TCP&#xff1a;可靠的有序传输 TCP是一种面向连接的协议&#xff0c;旨在提供可靠、有序的数据传输。它通过以下方式实现这一目标&#xff1a; 1. 连接建立和维护 在使用TCP传输数据之前&#xff0c;必须先建立连接。这个过程包括三次握手&#xff0c;即客户端和服务器之间…...

c++内存对齐

原文在这里。https://blog.csdn.net/WangErice/article/details/103598081 但是内容有错误。我在自己的这里修改并变成红色了。 内存在使用过程并不是单一的依次排列&#xff0c;而是按照某种既定的规则来进行对齐&#xff0c;以方便快速访问.内存的对齐原则有以下三条&#…...

leetcode 33. 搜索旋转排序数组

2023.9.26 本题暴力法可以直接A&#xff0c;但是题目要求用log n的解法。 可以想到二分法&#xff0c;但是一般二分法适用于有序数组的&#xff0c;这里的数组只是部分有序&#xff0c;还能用二分法吗&#xff1f; 答案是可以的。因为数组是经过有序数组旋转得来的&#xff0c;…...

VCS flow学习

VCS VCS 是IC从业者常用软件&#xff0c;该篇文章是一个学习记录&#xff0c;会记录在使用过程中各种概念及options。 VCS Flow VCS Flow 可以分为Two-step Flow和Three-step Flow两类。 两步法 两步法只支持Verilog HDL和SystemVerilog的design&#xff0c;两步法主要包括…...

微信扫码关注公众号登录功能php实战分享

1、安装easywechat 基于easywechat框架开发,首先下载安装easywechat composer require overtrue/wechat 2、公众号配置 先去公众号后台基本配置/ 填写服务器配置配置接口,需要是线上能正确收到微信推送消息的地址,关注如果有关注、扫码、收到消息等事件都会推送到该地址…...

Git 精简快速使用

安装 Git 忽略&#xff0c;自行搜索 新建项目&#xff0c;或者在仓库拉取项目&#xff0c;进入到项目目录 Github 给出的引导&#xff0c;新项目和旧项目 echo "# testgit" >> README.md git init git add README.md git commit -m "first commit"…...

线性约束最小方差准则(LCMV)波束形成算法仿真

常规波束形成仅能使得主波束对准目标方向&#xff0c;从而在噪声环境下检测到目标&#xff0c;但无法对复杂多变的干扰做出响应&#xff0c;所以不能称之为真正意义上的自适应滤波。自适应阵列处理指的是采用自适应算法对空间阵列接收的混合信号进行处理&#xff0c;又可称为自…...

什么是内容运营?

关于内容运营&#xff0c;在不同种类的公司&#xff0c;侧重点也不一样。 电商平台的内容运营岗更偏内容营销&#xff1b;产品功能比较简单的公司&#xff0c;内容运营和新媒体运营的岗位职责差不多&#xff1b;而内容平台的内容运营更多的是做内容的管理和资源整合。...

搭建安信可小安派Windows 开发环境

搭建小安派Windows 开发环境 Ai-Pi-Eyes 系列是安信可开源团队专门为Ai-M61-32S设计的开发板&#xff0c;支持WiFi6、BLE5.3。所搭载的Ai-M61-32S 模组具有丰富的外设接口&#xff0c;具体包括 DVP、MJPEG、Dispaly、AudioCodec、USB2.0、SDU、以太网 (EMAC)、SD/MMC(SDH)、SP…...

XML文件反序列化读取

原始XML文件 <?xml version"1.0" encoding"utf-8" ?> <School headmaster"王校长"><Grade grade"12" teacher"张老师"><Student name"小米" age"18"/><Student name&quo…...

会议剪影 | 思腾合力受邀参加2023第二届世界元宇宙大会并作主题演讲

由中国仿真学会、中国指挥与控制学会和北京理工大学共同主办&#xff0c;上海市嘉定区安亭镇人民政府和中国仿真学会元宇宙专业委员会承办的第二届世界元宇宙大会于2023年9月20日-22日在上海安亭举行。 大会以“虚实相生、产业赋能”为主题&#xff0c;聚焦元宇宙关键技术发展的…...

专业级跨平台资源下载利器:res-downloader一站式网络资源嗅探解决方案

专业级跨平台资源下载利器&#xff1a;res-downloader一站式网络资源嗅探解决方案 【免费下载链接】res-downloader 资源下载器、网络资源嗅探&#xff0c;支持微信视频号下载、网页抖音无水印下载、网页快手无水印视频下载、酷狗音乐下载等网络资源拦截下载! 项目地址: http…...

HTTP自动化测试架构:基于QD框架的HAR模板规模化治理策略

HTTP自动化测试架构&#xff1a;基于QD框架的HAR模板规模化治理策略 【免费下载链接】templates 基于开源新版 QD 框架站发布的公共har模板库&#xff0c;仅供示例 项目地址: https://gitcode.com/GitHub_Trending/templa/templates 在当今云原生和微服务架构盛行的时代…...

Artichoke 未来展望:这个创新 Ruby 实现的路线图和愿景 [特殊字符]

Artichoke 未来展望&#xff1a;这个创新 Ruby 实现的路线图和愿景 &#x1f680; 【免费下载链接】artichoke &#x1f48e; Artichoke is a Ruby made with Rust 项目地址: https://gitcode.com/gh_mirrors/ar/artichoke Artichoke 是一个用 Rust 编写的创新 Ruby 实现…...

iOS折叠动画终极指南:用Popping打造惊艳视觉效果

iOS折叠动画终极指南&#xff1a;用Popping打造惊艳视觉效果 【免费下载链接】popping A collection of animation examples for iOS apps. 项目地址: https://gitcode.com/gh_mirrors/po/popping 想要为你的iOS应用添加令人惊艳的折叠动画效果吗&#xff1f;Popping项目…...

5分钟搞定高精度人脸检测:MogFace工具零基础部署与使用教程

5分钟搞定高精度人脸检测&#xff1a;MogFace工具零基础部署与使用教程 1. 前言&#xff1a;为什么选择MogFace&#xff1f; 人脸检测技术已经广泛应用于我们的日常生活中&#xff0c;从手机相册的人脸分类到社交媒体的美颜滤镜&#xff0c;都离不开这项基础技术。然而在实际…...

OpenClaw技能市场探索:GLM-4.7-Flash加持的10个实用插件

OpenClaw技能市场探索&#xff1a;GLM-4.7-Flash加持的10个实用插件 1. 为什么需要关注OpenClaw技能市场&#xff1f; 当我第一次接触OpenClaw时&#xff0c;最让我惊喜的不是它的基础功能&#xff0c;而是它丰富的技能市场生态。作为一个长期使用各类自动化工具的技术爱好者…...

Java实现Redis延迟队列:从原理到高可用架构

在现代分布式系统中&#xff0c;延迟队列是一种至关重要的组件。它允许我们将消息或任务放入队列&#xff0c;直到指定的延迟时间到达后才被消费。这种机制广泛应用于订单超时自动取消、支付后定时发送通知、任务重试等场景。 虽然RabbitMQ和RocketMQ等专业消息中间件都支持延迟…...

网络异常排查:快速定位域连接问题

问题描述与初步排查网络位置异常通常表现为计算机无法正确识别当前所在的AD域环境&#xff0c;导致访问域资源受限或登录问题。常见症状包括系统托盘显示“无法访问域”、组策略无法应用、DNS解析失败等。检查计算机是否能够ping通域控制器的主机名和IP地址。使用nslookup命令验…...

ComfyUI-TeaCache:基于时间步感知缓存的扩散模型推理加速技术实现1.5-3倍性能提升

ComfyUI-TeaCache&#xff1a;基于时间步感知缓存的扩散模型推理加速技术实现1.5-3倍性能提升 【免费下载链接】ComfyUI-TeaCache 项目地址: https://gitcode.com/gh_mirrors/co/ComfyUI-TeaCache 在AI图像与视频生成领域&#xff0c;扩散模型的推理速度一直是制约创作…...

华硕笔记本CPU过热?G-Helper降压调优终极指南帮你降温10℃

华硕笔记本CPU过热&#xff1f;G-Helper降压调优终极指南帮你降温10℃ 【免费下载链接】g-helper Lightweight Armoury Crate alternative for Asus laptops. Control tool for ROG Zephyrus G14, G15, G16, M16, Flow X13, Flow X16, TUF, Strix, Scar and other models 项目…...