代码随想录 动态规划 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、代码封装 前言 使用旧方法对视频信息进行系统化管理已经不再让人们信赖了,把现在的网络信息技术运…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
