【动态规划】不同路径,编辑距离题解及代码实现

news/2024/10/30 15:33:39/

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。

🌈个人主页:主页链接

🌈算法专栏:专栏链接

     我会一直往里填充内容哒!

🌈LeetCode专栏:专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出

🌈代码仓库:Gitee链接

🌈点击关注=收获更多优质内容🌈

目录

题目:不同路径

题解:

代码实现:

 题目:编辑距离

 题解:

先来看看跳过

 再来看看插入

再来看看删除

最后来看看替换操作:

代码实现:

完结撒花:


两题由简单到难得DP问题!助我们拿下DP!

题目:不同路径

题解:

这题非常的简单,算是动态规划里的入门题了,但我们再来认真复习一下动态规划的内容。

首先明确状态,根据题所给,我们的状态就是dp[i][j]:走到第i行第j列时,有多少种路径。

那我想要走到第i行第j列只能从以下两种方法走到

所以状态转移方程就出来了:dp[i][j]=dp[i-1][j]+dp[i][j-1]

那么这道题不就迎刃而解了嘛?

但是,我们还得初始化下初始的情况。

若要走到(0,0)有几条路?显然只有一条

那走到(i,0),与(0,j)呢?也只有一条,因为,只能向右或者向左走,所以将其都初始化为1即可。这样base case也完成了。这题也就结束了。

代码实现:

#include <algorithm>
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>>dp(m,vector<int>(n));dp[0][0]=1;for(int i=0;i<m;i++)dp[i][0]=1;for(int i=0;i<n;i++)dp[0][i]=1;for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
};

 题目:编辑距离

 题解:

 这题有点困难,但也没有想象中的那么难。仍然跟着三板斧走:状态(dp的含义) 状态转移方程 ,以及base case

首先来分析下题目:

将word1变成word2最短要几步?

那么显而易见,这里的dp状态就是为,将word1的前i个与word2的前j个字母对齐最少 需要几步。

对字符串处理有三种方法:插入删除替换,这里还有一个隐藏的方法,跳过(当两个字符相同的时候就可以执行跳过这一步骤)

先来看看跳过

 他的情况就是为:当word[i]==word[j]时,操作数就与前一个字母相同,即dp[i][j]=dp[i-1][j-1]

 再来看看插入

当word1[i]!=word[j]时, 将word[j]插入,此时将word[j]导致的就是,i指向为插入为i+1,与此时的j比较,相等,第一种跳过的情况,所以i=i+1-1也就是i,而j变成了j-1.说了这么多也就是想说,插入的那个字母表示已经比对过了,zhihj往前跳一个与此时的i进行比较即可.(插入是我觉得最难的地方,不懂得uu门可以自己画图理解一下) 

所以其dp方程为DP[i][j]=DP[i][j-1]+1

再来看看删除

这个就很好理解了,把i指向的字母删掉,操作数加一,之后继续将i-1与j比较.

所以DP方程为:DP[i][j]=DP[i-1][j] +1

最后来看看替换操作:

 这个和skip有点像,因为他们的DP方程都相同,唯一的区别就在于,操作数是否要加一(替换需要加一,而skip并不需要).

将i指向的字母替换成j指向的字母,替换后两个字母相同,此时执行skip操作即可

所以其dp方程为:DP[i][j]=DP[i-1][j-1]+1

 到此四种情况都讲完了,还差最后一板斧,base case;

这里的base case也非常好理解,

当i字符串比j字符串要短的时候,也就是dp[0][j],此时要操作的数目就是插入j个字符,操作数为j,所以dp[0][j]=j

当j字符串比i字符串要短的时候.也就是dp[i][0],此时要操作的数目就是删除i个字符,操作数为i,所以dp[i][0]=i

至此,三板斧已经全部解决完,其实就是若skip情况出现,则用其结果,若没出现,则其他三种一个个试过去找最小的情况.

接下来看看代码中值得注意的地方

代码实现:

#include <algorithm>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1));int l1=word1.size();int l2=word2.size();if(l1*l2==0)return l1+l2;for(int i=0;i<=l1;i++)dp[i][0]=i;for(int j=0;j<=l2;j++)dp[0][j]=j;for(int i=1;i<=l1;i++){for(int j=1;j<=l2;j++){//skip情况if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];//dp从1开始,对应的word为-1   //replace delete insert 三者找最小的可能else dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));}}return dp[l1][l2];}
};

完结撒花:

🌈本篇博客的内容【动态规划:不同路径,编辑距离题解及代码实现】已经结束。

🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。

🌈诸君,山顶见!


http://www.ppmy.cn/news/32559.html

相关文章

SpringBoot整合RabbitMQ,包含:初始化定义队列,消息发送,消息接收 --柚子真好吃

一、搭建RabbitMq服务并创建账号 服务采用Docker临时搭建&#xff0c;版本采用3.8&#xff0c;命令如下 拉取镜像 docker pull rabbitmq:3.8.34-management创建容器 由于我使用的是 Docker Desktop 可通过可视化界面创建容器&#xff0c;将端口对应好即可&#xff0c;如下图&…

Opencv项目实战:22 物体颜色识别并框选

目录 0、项目介绍 1、效果展示 2、项目搭建 3、项目代码展示与部分讲解 Color_trackbar.py bgr_detector.py test.py 4、项目资源 5、项目总结 0、项目介绍 本次项目要完成的是对物体颜色的识别并框选&#xff0c;有如下功能&#xff1a; &#xff08;1&#xff09;…

JavaWeb学习-JSP

JSP作用 JSP全称为Java Server Pages即Java服务器页面&#xff0c;主要作用是代替Servlet程序回传HTML页面的数据&#xff0c;因为Servlet程序回传HTML页面数据非常繁琐&#xff0c;开发成本和维护成本较高。 package com.pero.jsp.jsp_javaweb;import jakarta.servlet.*; im…

C++模拟实现红黑树

目录 介绍----什么是红黑树 甲鱼的臀部----规定 分析思考 绘图解析代码实现 节点部分 插入部分分步解析 ●父亲在祖父的左&#xff0c;叔叔在祖父的右&#xff1a; ●父亲在祖父的右&#xff0c;叔叔在祖父的左&#xff1a; 测试部分 整体代码 介绍----什么是红黑树 红…

IDEA安装JRebel实现热部署,自动reload和recompile

利用JRebel插件实现代码及时编译功能&#xff0c;帮助我们在开发过程中节省项目重启时间&#xff0c;提高开发效率。JRebel插件实现及时编译&#xff0c;帮助我们在开发过程中节省项目重启时间&#xff0c;提高开发效率。一、安装插件安装流程&#xff1a;1.下载安装JRebel插件…

好记性不如烂笔头(2)

概述&#xff1a;用来记录一些小技巧。 1.查看MyBatis执行的sql 类&#xff1a;org.apache.ibatis.mapping.MappedStatement方法&#xff1a;getBoundSql(Object parameterObject)在IDEA的Evaluate Expression查看sql&#xff1a;boundSql.getSql() 2.maven仓库地址为https&…

解决 IDA 防F5转伪C笔记

某app砸壳后放到IDA,根据堆栈查到该位置如下; G调到,0x1b81bcc 看下: BR 调到后面 x8 x9地址,汇编指令; 找到x9的地址,然后减去基地址也就是首地址,得到便宜地址; hook x9: var moduleAddr = Module.findBaseAddress("XX"); var line = moduleAddr.add

面试重难点问题(C++)

持续更新&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 网络部分 1.问&#xff0c;四次挥手的过程&#xff0c;和双方状态变化&#xff1f; 挥手这前&#xff0c;两边都是established状态&#xff0c;客户端发起断开请求&#xff0c;向服务器发送fin请求&…