首页 > 其他分享 >代码随想录 day58 判断子序列 不同的子序列

代码随想录 day58 判断子序列 不同的子序列

时间:2024-02-22 22:34:32浏览次数:31  
标签:结尾 元素 随想录 day58 为空 序列 dp

判断子序列

dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。

if (s[i - 1] == t[j - 1])
t中找到了一个字符在s中也出现了
if (s[i - 1] != t[j - 1])
相当于t要删除元素,继续匹配

不同的子序列

dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

s[i - 1] 与 t[j - 1]相等
s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]相等时,dp[i][j]可以有两部分组成。

一部分是用s[i - 1]来匹配,那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母,所以只需要 dp[i-1][j-1]。
一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j]。

因为是在s里删元素找t的特征串而不是想法 所以不用考虑t[j - 1]

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
+左边是考虑使用当前元素 右边是不考虑使用当前元素
如:s:“bagg” t:“bag”

初始化
dp[i][0] = 1 如果t为空 那么就只能吧s全删了得到t 也就是只有一种方法
dp[0][j] = 0 这里不考虑t为空 那么在s为空的情况下 s无论如何也得不到t

标签:结尾,元素,随想录,day58,为空,序列,dp
From: https://www.cnblogs.com/mingtiao/p/18028362

相关文章

  • 代码随想录算法训练营day02 | leetcode 977. 有序数组的平方、35.搜索插入位置、34.在
    题目链接:977.有序数组的平方-简单题目描述:给你一个按非递减顺序排序的整数数组nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。示例1:输入:nums=[-4,-1,0,3,10]输出:[0,1,9,16,100]解释:平方后,数组变为[16,1,0,9,100]排序后,数组变为[0,1,9,16,100]......
  • 代码随想录算法训练营第二十五天| 216.组合总和III 17.电话号码的字母组合
    组合总和III题目链接:216.组合总和III-力扣(LeetCode)思路:仿照昨天的递归模板写的,同样是for循环横向遍历,递归纵向遍历。注意当k>n时要直接跳出,否则会判断栈溢出。额外发现一个问题就是在累加sum时,用for(autoi:path)sum+=path[i];会出现奇怪数字,原因是auto遍历用法错误,正确写......
  • 对象序列化内存占用问题
     一般而言,前端发起一个查询,后端接收请求而后去数据库检索并得到结果集,之后序列化为字符串返回给前端展示。在序列化方法接收一个集合到序列化(比如这里是json)的过程中,内存占用会增大吗?肯定会的,总体而言我们new出的对象,对象引用的字符、数字等都是存放在堆内存中;未序列化这些对......
  • [dotnet-Sec]初探反序列化
    [dotnet-Sec]初探反序列化参考Github上y4✌的开源笔记,狠狠学!环境搭建.NET:5.0IDE:Rider(JB家族)新建项目选择.NETCore(支持跨平台)下的控制台应用程序,然后创建这是接触到的关于dotnet的第一个反序列化demo,使用的是BinaryFormatter生成二进制流//Disablethewarning.#pragma......
  • day39 动态规划part2 代码随想录算法训练营 63. 不同路径 II
    题目:63.不同路径II我的感悟:题目不难,就是不知道哪个煞笔,把路拦截死了,并且入口就放石头,我真是吐了。理解难点:初始值的遇到障碍要Break其他我写的没错边界考虑:还有入口和出口有障碍物的话,要直接返回0.听课笔记:差不多,考虑的点就是:初始值后面为break开头和结尾有障......
  • R语言用LOESS(局部加权回归)季节趋势分解(STL)进行时间序列异常检测
    原文链接:http://tecdat.cn/?p=22632 原文出处:拓端数据部落公众号这篇文章描述了一种对涉及季节性和趋势成分的时间序列的中点进行建模的方法。我们将对一种叫做STL的算法进行研究,STL是"使用LOESS(局部加权回归)的季节-趋势分解"的缩写,以及如何将其应用于异常检测。其基本思......
  • 代码随想录算法训练营第二十五天 | 17.电话号码的字母组合 , 216.组合总和III
    216.组合总和III 已解答中等 相关标签相关企业 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:只使用数字1到9每个数字 最多使用一次返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回......
  • 读论文-序列感知推荐系统(Sequence-Aware Recommender Systems)
    前言今天读的论文为一篇于2018年发表在(ACMcomputingsurveys(CSUR))的论文,这篇文章主要讲述了序列感知推荐系统(Sequence-AwareRecommenderSystems)的研究和应用。文章首先介绍了推荐系统在实际中的应用背景,然后指出了传统推荐系统在处理用户行为序列信息方面的局限性。接着,文......
  • 代码随想录算法训练营day 1 | 704 二分查找 27 删除元素
    704二分查找数组基础数组空间地址连续、随机访问时间复杂度O(1)、删除和移动时间复杂度O(n)vector和array区别:vector底层实现为array;array是栈上开辟空间、vector是堆上开辟空间;array不支持迭代器访问,支持指针和索引、vector还支持迭代器访问二分查找适用场景有序数组、数组......
  • 大数分析(6)——Y序列
    前言然后是Y序列,0-Y可以直接与BMS相互转换,而基本的1-Y序列(常说的Y序列就是这个)便有着极大的提升,甚至可以提升到n-Y,\(\omega-\)YBMS和Y序列,便如同强者界的天道、奥加一般(同样的,后面由于缺少标定记号可能会跳过大段/直接开鸽阶差为1的情况请参考PrSS,完全一致,极限同样是\(\epsil......