Day48 | 动态规划 :线性DP 编辑距离

server/2024/12/26 18:24:11/

Day48 | 动态规划 :线性DP 编辑距离

动态规划应该如何学习?-CSDN博客

本次题解参考自灵神的做法,大家也多多支持灵神的题解

最长公共子序列 编辑距离_哔哩哔哩_bilibili

动态规划学习:

1.思考回溯法(深度优先遍历)怎么写

注意要画树形结构图

2.转成记忆化搜索

看哪些地方是重复计算的,怎么用记忆化搜索给顶替掉这些重复计算

3.把记忆化搜索翻译成动态规划

基本就是1:1转换

文章目录

  • Day48 | 动态规划 :线性DP 编辑距离
    • 72.编辑距离
      • 思路分析(子问题):
      • 1.回溯 DFS
      • 2.记忆化搜索
      • 3.1:1翻译为动态规划

72.编辑距离

不知道怎么回事从困难题目直接变成中等题目了

72. 编辑距离 - 力扣(LeetCode)

思路分析(子问题):

设两个字符串分别是s和t

对应的最后一个字母分别是x和y

dfs(x,y)那就是s以x结尾,t以y结尾的两个字符串由s变成t的需要的最小操作数了

举个例子

word1 = "horse", word2 = "ros"

x==1,y==2那就是s==ho变到t==ros需要的最小操作数了

可以先看看昨天这篇题解

Day47 | 动态规划 :线性DP 最长公共子序列&&最长公共子数组-CSDN博客

//设两个字符串分别是s和t//对应的最后一个字母分别是x和ydfs(x,y)那就是s以x结尾,t以y结尾的两个字符串的最长公共子序列的长度了那就有四种情况1.选x这个字母也选y这个字母2.不选x不选y3.选x不选y4.选y不选x如果s[x]==t[y],那肯定就是选x也选y,那肯定就是dfs(x,y)=dfs(x-1,y-1)+1如果说s[x]!=t[y],那么就是剩下三种情况里面取一个最大值dfs(x,y)=max(dfs(x-1,y-1),dfs(x,y-1),dfs(x-1,y))再仔细一看,其实dfs(x,y-1),dfs(x-1,y)包含了dfs(x-1,y-1),所以不需要这个了dfs(x,y)=max(dfs(x,y-1),dfs(x-1,y))不明白可以举例
dfs(x,y-1)=max(dfs(x-1,y-1),dfs(x,y-2))
其中包含了x-1,y-1的情况

现在重新思考一下选或不选这个过程

1.s[x]==t[y]

那说明我们什么都不用做,因为这两个字符本身就是相等的,我们不需要删除也不需要插入也不需要替换

dfs(x,y)=dfs(x-1,y-1)

2.s[x]!=t[y]

那我们需要在插入,删除,替换这三种操作中选择一个最小值,选择完最小值之后要+1,因为我们肯定会进行这三种操作的一种

dfs(x,y)=min(dfs(x,y-1),dfs(x-1,y),dfs(x-1,y-1))+1
//			插入			删除			替换

插入操作理解:

在s中插入一个字母z让它和t的第y个字母相同

(可以这么理解:因为是s要变成t,插入是在x的下一位置(x+1处)插入,我们在x+1处插入了t[y]使得这两个字符串相等,所以我们下次递归的时候就不需要看t[y]了,直接从t[y-1]开始,因为t[y]和s[x+1]是相等的)

dfs(x,y-1)+1

举个例子

s=exection -> t=execution (插入 'u')

从后往前递归,递归到x=3,y=4,即x指向c,y指向u的时候

dfs(x,y)=dfs(3,4)的意思就是

exec变成execu需要的最小操作数

dfs(x,y-1)=dfs(3,3)

exec变成exec需要的操作数

dfs(x,y)=dfs(x,y-1)+1

意思就是

exec变成exec需要的操作数+在s中插入一个u这个操作

删除操作理解:

dfs(x-1,y)+1

在s中删除一个字母,就是把和t[y]不一样的那个字母给删掉

和插入同理

(可以这么理解:因为是s要变成t,删除是删s[x],我们在x处删除了s[x],所以我们下次递归的时候就不需要看s[x]了,直接从s[x-1]开始)

举例:

s=rorse -> t=rose (删除 'r')

那么

dfs(2,1)

s=ror -> t=ro (删除 'r')

dfs(1,1)+1

s=ro -> t=ro 

替换操作理解:

dfs(x-1,y-1)+1

把s[x]换成和t[y]一样的字母

这个比较简明,就是用y替换掉了x,然后就都不看这两个了,直接去看两个字符串前面了

1.回溯 DFS

1.返回值和参数

dfs(i,j)那就是s以i结尾,t以j结尾的两个字符串由s变成t的需要的最小操作数了

int dfs(int i,int j,string &s,string &t)

2.终止条件

s为空字符串,那s就需要插入j+1个字符变成t

t为空字符串,那么s就需要删除i+1个字符变成t

		if(i<0)return j+1;if(j<0)return i+1;

3.本层逻辑

相等就不需要操作,不相等就三种操作里面选最小值

		if(s[i]==t[j])return dfs(i-1,j-1,s,t);elsereturn min(min(dfs(i,j-1,s,t),dfs(i-1,j,s,t)),dfs(i-1,j-1,s,t))+1;

完整代码:

当然,这是超时的

class Solution {
public:int dfs(int i,int j,string &s,string &t,vector<vector<int>>& dp){if(i<0)return j+1;if(j<0)return i+1;if(dp[i][j]!=-1)return dp[i][j];if(s[i]==t[j])return dp[i][j]=dfs(i-1,j-1,s,t,dp);elsereturn dp[i][j]=min(min(dfs(i,j-1,s,t,dp),dfs(i-1,j,s,t,dp)),dfs(i-1,j-1,s,t,dp))+1;}int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size(),vector<int>(word2.size(),-1));return dfs(word1.size()-1,word2.size()-1,word1,word2,dp);}
};
//lambda
class Solution {
public:int minDistance(string word1, string word2) {function<int(int,int)> dfs=[&](int i,int j)->int{if(i<0)return j+1;if(j<0)return i+1;if(word1[i]==word2[j])return dfs(i-1,j-1);elsereturn min(min(dfs(i,j-1),dfs(i-1,j)),dfs(i-1,j-1))+1;}; return dfs(word1.size()-1,word2.size()-1);}
};

2.记忆化搜索

就是搞一个哈希表dp,全都初始化为-1,每次返回前给哈希表dp赋值,碰到不是-1的那就是算过的,那就直接返回计算过的结果,不需要再次递归了

class Solution {
public:int dfs(int i,int j,string &s,string &t,vector<vector<int>> &dp){if(i<0||j<0)return 0;if(dp[i][j]!=-1)return dp[i][j];if(s[i]==t[j])return dp[i][j]=dfs(i-1,j-1,s,t,dp)+1;elsereturn dp[i][j]=max(dfs(i-1,j,s,t,dp),dfs(i,j-1,s,t,dp));}int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),-1));return dfs(text1.size()-1,text2.size()-1,text1,text2,dp);}
};
//lambda
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size(),vector<int>(word2.size(),-1));function<int(int,int)> dfs=[&](int i,int j)->int{if(i<0)return j+1;if(j<0)return i+1;if(dp[i][j]!=-1)return dp[i][j];if(word1[i]==word2[j])return dp[i][j]=dfs(i-1,j-1);elsereturn dp[i][j]=min(min(dfs(i,j-1),dfs(i-1,j)),dfs(i-1,j-1))+1;}; return dfs(word1.size()-1,word2.size()-1);}
};

3.1:1翻译为动态规划

1.确定dp数组以及下标的含义

dp[i][j]就是dfs(I,j)

下标从1开始,下标0记录对应回溯终止条件处的赋值

2.确定递推公式

和dfs中也是对应的

				if(word1[i]==word2[j])dp[i+1][j+1]=dp[i][j];else    dp[i+1][j+1]=min(min(dp[i+1][j],dp[i][j+1]),dp[i][j])+1;

3.dp数组如何初始化

根据回溯终止条件进行初始化

s从空变到t就是插入i哥

t为空,s变过去就是删除i个

注意我们的下标是从1开始的,所以初始化时候要写小于等于,不然会有两个值没有初始化导致报错

		vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));for(int i=0;i<=word2.size();i++)dp[0][i]=i;for(int i=0;i<=word1.size();i++)dp[i][0]=i;

4.确定遍历顺序

		for(int i=0;i<word1.size();i++)for(int j=0;j<word2.size();j++)if(word1[i]==word2[j])dp[i+1][j+1]=dp[i][j];else    dp[i+1][j+1]=min(min(dp[i+1][j],dp[i][j+1]),dp[i][j])+1;

完整代码

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));for(int i=0;i<=word2.size();i++)dp[0][i]=i;for(int i=0;i<=word1.size();i++)dp[i][0]=i;for(int i=0;i<word1.size();i++)for(int j=0;j<word2.size();j++)if(word1[i]==word2[j])dp[i+1][j+1]=dp[i][j];else    dp[i+1][j+1]=min(min(dp[i+1][j],dp[i][j+1]),dp[i][j])+1;return dp[word1.size()][word2.size()];}
};

http://www.ppmy.cn/server/146251.html

相关文章

【青牛科技】电动工具电流反馈型相位控制电路D2010

概述&#xff1a; D2010是一块相位控制集成电路&#xff0c;采用双级工艺。具有负载电流保护、软启动等功能。广泛应用于机床马达的控制。 主要特点: 全波电流感应 主电源可调软启动 防止过流及过高输出程控电流大小&#xff0c; 电压与电流同步 自动触发开关内部电压监控申流…

电机瞬态分析基础(3):空间矢量

1. 空间矢量 空间矢量的概念在交流电机分析与控制中具有非常重要的作用。将各相的电压、电流、磁链等电磁量用空间矢量表达&#xff0c;可以使三相感应电机的动态方程表达更简洁&#xff0c;为电机的分析与控制带来方便&#xff0c;并有助于对交流电机的矢量控制、直接转矩控制…

【Python爬虫五十个小案例】爬取中国天气网城市天气

博客主页&#xff1a;小馒头学python 本文专栏: Python爬虫五十个小案例 专栏简介&#xff1a;分享五十个Python爬虫小案例 引言 天气数据在很多领域都非常重要&#xff0c;比如天气预报、旅游、健康等。通过爬取天气网站的公开数据&#xff0c;可以方便地获取各地的天气情…

GPT分区、格式化与自动挂载

GPT分区、格式化与自动挂载 操作场景前提条件操作步骤 操作场景 云硬盘容量大于2TiB时&#xff0c;只能使用parted工具为磁盘新建GPT分区。 前提条件 云硬盘已挂载到云服务器上。 操作步骤 使用root用户登录进入云服务器&#xff1b;安装parted工具&#xff1b; # 检查pa…

GateWay使用手册

好的&#xff0c;下面是优化后的版本。为了提高可读性和规范性&#xff0c;我对内容进行了结构化、简化了部分代码&#xff0c;同时增加了注释说明&#xff0c;便于理解。 1. 引入依赖 在 pom.xml 中添加以下依赖&#xff1a; <dependencies><!-- Spring Cloud Gate…

路由引入中次优路由和路由环路问题

A公司用的是IS-IS&#xff0c;B公司用的是OSPF&#xff0c;现在这两个公司要合并&#xff0c;网络要相通 项目目标 前期准备 配置IP地址&#xff1a;完成IP地址规划&#xff0c;A公司和B公司内部网络通过路由器R2和R4环回接口模拟。配置路由器接口的IP地址并测试所有直连链路的…

windows11 使用体验记录

好的地方&#xff1a; UI上字体风格貌似更好看了&#xff0c;文件夹增加了多个标签&#xff0c;类似于浏览器既可以打开多个窗口&#xff0c;也可以在同一个窗口中打开多个标签页 不好的地方&#xff1a; 桌面右下角点击日期时间&#xff0c;显示日期&#xff0c;时间呢&…

大语言模型LLM的微调中 QA 转换的小工具 xlsx2json.py

在训练语言模型中&#xff0c;需要将文件整理成规范的文档&#xff0c;因为文档本身会有很多不规范的地方&#xff0c;为了训练的正确&#xff0c;将文档进行规范处理。代码的功能是读取一个 Excel 文件&#xff0c;将其数据转换为 JSON 格式&#xff0c;并将 JSON 数据写入到一…