代码随想录 动态规划 part16
583. 两个字符串的删除操作
给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
思路:dp[i][j]数组表示使得 word1[:i] 和 word2[:j] 相同所需的最小步数。当word1[i-1]==word2[j-1]时,dp[i][j] = dp[i-1][j-1], 当word1[i-1] != word2[j-1]时,dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1, 初始化dp[n][0] = dp[0][n] = n
class Solution:def minDistance(self, word1: str, word2: str) -> int:dp = [[0]*(len(word2)+1) for _ in range(len(word1) + 1)]for n in range(len(word1) + 1):dp[n][0] = nfor n in range(len(word2) + 1):dp[0][n] = nfor i in range(1, len(word1) + 1):for j in range(1, len(word2) + 1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1return dp[-1][-1]
72. 编辑距离
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
思路:接着上一道题,由于插入和替换需要的操作数是一样的(A删除 等价于 B插入),故只需要额外考虑替换一个字符。替换一个字符,就是转化为word1[i-1] =word2[j-1]的情况。故此时转移方程为:dp[i][j] = min(dp[i][j-1], dp[i-1][j],dp[i-1][j-1]) + 1
class Solution:def minDistance(self, word1: str, word2: str) -> int:dp = [[0]*(len(word2)+1) for _ in range(len(word1) + 1)]for n in range(len(word1) + 1):dp[n][0] = nfor n in range(len(word2) + 1):dp[0][n] = nfor i in range(1, len(word1) + 1):for j in range(1, len(word2) + 1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1return dp[-1][-1]
相关文章:
代码随想录 动态规划 part16
583. 两个字符串的删除操作 给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 思路:dp[i][j]数组表示使得 word1[:i] 和 word2[:j] 相同所需的最小步数。当word1[i-1]word2[…...
非 Prop 的属性
概念 父组件传给子组件的属性,但该属性没有在子组件 props 属性里定义。 属性继承 非 Prop 的属性默认情况下会被子组件的根节点继承,非 prop 的属性会保存在子组件 $attrs 属性里。 举例 子组件 date-picker 如下 <!-- 我是子组件 date-picker --&…...
初识Java 12-3 流
目录 终结操作 将流转换为一个数组(toArray) 在每个流元素上应用某个终结操作(forEach) 收集操作(collect) 组合所有的流元素(reduce) 匹配(*Match) 选…...
代码随想录算法训练营第42天|动态规划:01背包理论基础、动态规划:01背包理论基础(滚动数组)、416. 分割等和子集
动态规划:01背包理论基础 动态规划:01背包理论基础(滚动数组) 以上两个问题的代码未本地化保存 416. 分割等和子集 https://leetcode.cn/problems/partition-equal-subset-sum/ 复杂的解法 class Solution { public:bool ca…...
(详解)Linux常见基本指令(1)
目录 目录: 1:有关路径文件下的操作(查看,进入) 1.1 ls 1.2 pwd 1.3 cd 2:创建文件或目录 2.1 touch 2.2 mkdir 3:删除文件或目录 3.1 rm与rmdir 4:复制剪切文件 4.1 cp 4.2 mv 1:有关路径的操作 1 ls 指令 语法:ls [选项] [目录或文…...
紫光同创FPGA图像视频采集系统,提供2套PDS工程源码和技术支持
目录 1、前言免责声明 2、紫光同创FPGA相关方案推荐3、设计思路框架视频源选择OV7725摄像头配置及采集OV5640摄像头配置及采集动态彩条HDMA图像缓存输入输出视频HDMA缓冲FIFOHDMA控制模块 HDMI输出 4、PDS工程1详解:OV7725输入5、PDS工程2详解:OV5640输入…...
第一章 函数 极限 连续(解题方法须背诵)
(一)求极限的常用方法 方法1 利用有理运算法则求极限 方法2 利用基本极限求极限 方法3 利用等价无穷小求极限 方法4 利用洛必达法则求极限 方法5 利用泰勒公式求极限 方法6 利用夹逼准则求极限 方法7 利用定积分的定义求极限 方法8 利用单调有界…...
selenium +IntelliJ+firefox/chrome 环境全套搭配
1第一步:下载IntelliJ idea 代码编辑器 2第二步:下载浏览器Chrome 3第三步:下载JDK 4第四步:配置环境变量(1JAVA_HOME 2 path) 5第五步:下载Maven 6第六步:配置环境变量&#x…...
CentOS 7 停止维护后如何平替你的生产系统?
Author:rab 目录 前言一、Debian 家族1.1 Debian1.2 Ubuntu 二、RHEL 家族2.1 Red Hat Enterprise Linux2.2 Fedora2.3 CentOS2.4 Rocky Linux2.5 AlmaLinux 三、如何选择?思考? 前言 CentOS 8 系统 2021 年 12 月 31 日已停止维护服务&…...
第81步 时间序列建模实战:Adaboost回归建模
基于WIN10的64位系统演示 一、写在前面 这一期,我们介绍AdaBoost回归。 同样,这里使用这个数据: 《PLoS One》2015年一篇题目为《Comparison of Two Hybrid Models for Forecasting the Incidence of Hemorrhagic Fever with Renal Syndr…...
135.【JUC并发编程_01】
JUC 并发编程 (一)、基本概述1.概述 (二)、进程与线程1.进程与线程(1).进程_介绍(2).线程_介绍(3).进程与线程的区别 2.并行和并发(1).并发_介绍(2).并行_介绍(3).并行和并发的区别 3.应用(1).异步调用_较少等待时间(2).多线程_提高效率 (三)、Java 线程1.创建线程和运行线程(1…...
VC++创建windows服务程序
目录 1.关于windows标准可执行程序和服务程序 2.服务相关整理 2.1 VC编写服务 2.2 服务注册 2.3 服务卸载 2.4 启动服务 2.5 关闭服务 2.6 sc命令 2.7 查看服务 3.标准程序 3.1 后台方式运行标准程序 3.2 查找进程 3.3 终止进程 以前经常在Linux下编写服务器程序…...
连续爆轰发动机
0.什么是爆轰 其反应区前沿为一激波。反应区连同前驱激波称为爆轰波。爆轰波扫过后,反应区介质成为高温高压的爆轰产物。能够发生爆轰的系统可以是气相、液相、固相或气-液、气-固和液-固等混合相组成的系统。通常把液、固相的爆轰系统称为炸药。 19世纪80年代初&a…...
交通物流模型 | 基于时空注意力融合网络的城市轨道交通假期短时客流预测
短时轨道交通客流预测对于交通运营管理非常重要。新兴的深度学习模型有效提高了预测精度。然而,大部分现有模型主要针对常规工作日或周末客流进行预测。由于假期客流的突发性和无规律性,仅有一小部分研究专注于假期客流预测。为此,本文提出一个全新的时空注意力融合网络(ST…...
2.2.1 嵌入式工程师必备软件
1 文件比较工具 在开发过程中,不论是对代码的对比,还是对log的对比,都是必不可不少的,通过对比,我们可以迅速找到差异,定位问题。当前常用的对比工具有:WinMerge,Diffuse,Beyond Compare,Altova DiffDog,AptDiff,Code Compare等。这里推荐使用Beyond Compare,它不…...
深入了解 RabbitMQ:高性能消息中间件
目录 引言:一、RabbitMQ 介绍二、核心概念三、工作原理四、应用场景五、案例实战 引言: 在现代分布式系统中,消息队列成为了实现系统间异步通信、削峰填谷以及解耦组件的重要工具。而RabbitMQ作为一个高效可靠的消息队列解决方案,…...
【数据库——MySQL】(14)过程式对象程序设计——游标、触发器
目录 1. 游标1.1 声明游标1.2 打开游标1.3 读取游标1.4 关闭游标1.5 游标示例 2. 触发器2.1 创建触发器2.2 修改触发器2.3 删除触发器2.4 触发器类型2.5 触发器示例 参考书籍 1. 游标 游标一般和存储过程一起配合使用。 1.1 声明游标 要使用游标,需要用到 DECLAR…...
位移贴图和法线贴图的区别
位移贴图和法线贴图都是用于增强模型表面细节和真实感的纹理贴图技术,但是它们之间也存在着差异。 1、什么是位移贴图 位移贴图:位移贴图通过在模型顶点上定义位移值来改变模型表面的形状。该贴图包含了每个像素的高度值信息,使得模型的细节…...
【typescript】面向对象(下篇),包含接口,属性的封装,泛型
假期第八篇,对于基础的知识点,我感觉自己还是很薄弱的。 趁着假期,再去复习一遍 面向对象:程序中所有的操作都需要通过对象来完成 计算机程序的本质就是对现实事物的抽象,抽象的反义词是具体。比如照片是对一个具体的…...
基于SpringBoot的视频网站系统
目录 前言 一、技术栈 二、系统功能介绍 用户信息管理 视频分享管理 视频排名管理 交流论坛管理 留言板管理 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 使用旧方法对视频信息进行系统化管理已经不再让人们信赖了,把现在的网络信息技术运…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
离线语音识别方案分析
随着人工智能技术的不断发展,语音识别技术也得到了广泛的应用,从智能家居到车载系统,语音识别正在改变我们与设备的交互方式。尤其是离线语音识别,由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力,广…...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
规则与人性的天平——由高考迟到事件引发的思考
当那位身着校服的考生在考场关闭1分钟后狂奔而至,他涨红的脸上写满绝望。铁门内秒针划过的弧度,成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定",构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...
