当前位置: 首页 > news >正文

代码随想录算法训练营day50|动态规划12

不同的子序列

给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。、

编辑距离中的删除元素,其实就是直接变数字,其只删除原来的较长的数组里的元素
在这里插入图片描述

递推模拟,使用s的最后一个元素匹配,或者删除最后一个元素看前面一个是否匹配
在这里插入图片描述

初始化,dp[i][0]=1表示s不为空,t为空,这样把s删到空就一定有一个,同理dp[0][i]=0,重叠部分dp[0][0]就等于空字符串匹配空字符串,为1

在这里插入图片描述

定义为int,出现了超时错误
在这里插入图片描述
在这里插入图片描述
所以可以用longlongint 的别名 uint64_t

class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1));for(int i=0;i<s.size();i++) dp[i][0]=1;for(int j=1;j<t.size();j++) dp[0][j]=0;for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]){dp[i][j]=dp[i-1][j-1]+dp[i-1][j];}else{dp[i][j]=dp[i-1][j];}}}return dp[s.size()][t.size()];}
};

两个字符串的删除操作

其实就是两个字符串都可以删除了

递推公式如下
在这里插入图片描述

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<=word1.size();i++) dp[i][0]=i;for(int j=0;j<=word2.size();j++) dp[0][j]=j;for(int i=1;i<=word1.size();i++){for(int j=1;j<=word2.size();j++){if(word1[i-1]==word2[j-1]) 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[word1.size()][word2.size()];}
};

思路二是,先求出公共子序列的长度,再用两个字符串的总长度减去公共子序列的长度

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

编辑距离(动规经典问题)

在这里插入图片描述
在这里插入图片描述

=为什么这道题不能采用上一题的思路二,先求出公共子序列的长度,再用两个字符串的总长度减去公共子序列的长度,因为很可能长度一样,但可以只替换一次就完成,但思路2会要求按着顺序删除


http://www.mrgr.cn/news/79390.html

相关文章:

  • Codeforces Round 991 (Div. 3)
  • 【C语言】C语言的变量和声明系统性讲解
  • 重磅更新:CnosDB 2.3.5.4 版本上线, 性能提升,问题修复一网打尽
  • 吉他初学者学习网站搭建系列(9)——如何用coze做一个网站助手
  • 事件循环(eventloop)
  • PySpark3.4.4_基于StreamingContext实现网络字节流中英文分词词频累加统计结果保存到数据库中
  • 游戏引擎学习第36天
  • Spring事务实现原理
  • 公共云提供商正在错失人工智能机遇
  • Linux 进程 ID(PID)查看 / 获取
  • 在做题中学习(77):快排
  • 万物可爬(以爬取浏览器井盖图片和豆瓣电影名字为例)
  • Next.js 系统性教学:构建应用的路由与页面管理
  • jeecg-uniapp 跨域问题解决方法记录
  • Let up bring up a linux.part2 [十一]
  • Codeforces Round 991 (Div. 3) F. Maximum modulo equality(区间gcd模板)
  • 《单片机原理及接口技术》(C51编程)(第三版)------张毅刚主编
  • Java线程的interrupt中断、wait-notify/all(源码级分析)
  • 容器第四天(day041)
  • 计算机网络复习6——应用层