动态规划16 | ● 583. 两个字符串的删除操作 ● *72. 编辑距离

2024-03-25 02:20

本文主要是介绍动态规划16 | ● 583. 两个字符串的删除操作 ● *72. 编辑距离,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html

  • 考点
    • 子序列问题
  • 我的思路
    • dp[i][j]的含义是,当两个字符串分别取前i和j个元素时,对应的最少相等删除步数是多少
    • 递推公式为,如果两个字符串第i和j个元素恰好相等,则dp值应等于不再考虑这两个元素的dp值即dp[i - 1][j - 1];如果i和j不相等,则dp值应等于删除任一元素后的dp值取较小者即min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
    • 初始化,由于递推公式依赖于当前元素在二维矩阵中的左上元素,因此需要对二维矩阵的第一行和第一列进行初始化,初始化原则是,如果当前位置两字符串的元素相等,则dp等于将较长者除当前元素外其它元素均删除所需要的步数;如果不相等,dp等于不考虑较长字符串当前元素后所需要的最少步数和不考虑较短字符串当前元素(也就是令较短字符串为空)时所需要的最少步数中取较小者
  • 视频讲解关键点总结
    • 和我的思路一致
  • 我的思路的问题
  • 代码书写问题
  • 可执行代码
class Solution:def minDistance(self, word1: str, word2: str) -> int:dp = [[0] * len(word2) for _ in range(len(word1))]if word1[0] == word2[0]:dp[0][0] = 0else:dp[0][0] = 2for i in range(1, len(word1)):if word1[i] == word2[0]:dp[i][0] = ielse:dp[i][0] = min(dp[i - 1][0] + 1, i + 2)for i in range(1, len(word2)):if word1[0] == word2[i]:dp[0][i] = ielse:dp[0][i] = min(dp[0][i - 1] + 1, i + 2)for i in range(1, len(word1)):for j in range(1, len(word2)):if word1[i] == word2[j]: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[-1][-1]

*72. 编辑距离

https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html

  • 考点
    • 子序列问题
  • 我的思路
    • dp含义和上一题整体思路相同
    • 递推公式两元素相等的情况和上一题相同,但是两元素不相等的情况只考虑到了删除当前word1元素的解法
    • 初始化较为简单,不展开说了
  • 视频讲解关键点总结
    • 我的思路的问题就在,递推公式里,如果两元素不相等,应该有三种处理方式(增、删、改),而我只实现了删的操作,其中增加一个元素也就是增加和word2当前元素相同的元素,也就是不需要考虑word2当前元素;删除也就是不考虑word1当前元素;改也就是不需要考虑word1和word2的当前元素
  • 我的思路的问题
    • 漏了两种情况
  • 代码书写问题
  • 可执行代码
class Solution:def minDistance(self, word1: str, word2: str) -> int:if word1 == '' and word2 == '':return 0elif word1 == '':return len(word2)elif word2 == '':return len(word1)dp = [[0] * len(word2) for _ in range(len(word1))]if word1[0] == word2[0]:dp[0][0] = 0else:dp[0][0] = 1for i in range(1, len(word1)):if word1[i] == word2[0]:dp[i][0] = ielse:dp[i][0] = dp[i - 1][0] + 1for i in range(1, len(word2)):if word1[0] == word2[i]:dp[0][i] = ielse:dp[0][i] = dp[0][i - 1] + 1for i in range(1, len(word1)):for j in range(1, len(word2)):if word1[i] == word2[j]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1)return dp[-1][-1]

这篇关于动态规划16 | ● 583. 两个字符串的删除操作 ● *72. 编辑距离的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/843564

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页);内聚的类型;关于码制的知识点;地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位:为1时表示在内存期间被访问过,为0时表示未被访问;修改位:为1时表示该页面自从被装入内存后被修改过,为0时表示未修改过。 置换页面时,最先置换访问位和修改位为00的,其次是01(没被访问但被修改过)的,之后是10(被访问了但没被修改过),最后是11。 2.内聚的类型 功能内聚:完成一个单一功能,各个部分协同工作,缺一不可。 顺序内聚:

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

动手学深度学习【数据操作+数据预处理】

import osos.makedirs(os.path.join('.', 'data'), exist_ok=True)data_file = os.path.join('.', 'data', 'house_tiny.csv')with open(data_file, 'w') as f:f.write('NumRooms,Alley,Price\n') # 列名f.write('NA