首页 > 其他分享 >代码随想录 day60 回文子串 最长回文子序列

代码随想录 day60 回文子串 最长回文子序列

时间:2024-02-24 22:02:15浏览次数:21  
标签:子串 初始化 遍历 随想录 day60 ij dp 回文

回文子串

dp[i][j]:[i, j]范围内为回文子串

递推式
分三种情况
①:ij相等 显然是回文
②:j - i < 1 且 s[i] == s[j] 显然是回文
③:j - i > 1 且 dp[i + 1][j - 1]为true 也就是当前两端元素相同 看元素内部是否是回文 如果是 显然是ij范围内是回文

初始化必须初始化false true的话整个字符串变成回文了

遍历i的时候一定要从下到上遍历,这样才能保证下一行的数据是经过计算的。

最长回文子序列

dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

两端如果相同 那么就迭代+2
如果不同 就分别考虑一端 求最大的值

初始化 ij下标相同时初始化为1 其他初始化为0

遍历i的时候一定要从下到上遍历,这样才能保证下一行的数据是经过计算的。

标签:子串,初始化,遍历,随想录,day60,ij,dp,回文
From: https://www.cnblogs.com/mingtiao/p/18031689

相关文章

  • 代码随想录算法训练营第二十七天 | 90.子集II , 78.子集, 93.复原IP地址
    93.复原IP地址 已解答中等 相关标签相关企业 有效IP地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。例如:"0.1.2.201" 和"192.168.1.1" 是 有效 IP地址,但是 "0.011.255.245"、"1......
  • 代码随想录算法训练营day03 | leetcode 203. 移除链表元素、707. 设计链表、206. 反转
    目录题目链接:203.移除链表元素-简单题目链接:707.设计链表-中等题目链接:206.反转链表-简单题目链接:203.移除链表元素-简单题目描述:给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6......
  • 代码随想录 day59 两个字符串的删除操作 编辑距离
    两个字符串的删除操作两种思路如果是以最长公共子序列去理解求出这个子序列长度然后原长减一下就行如果是直接正面求解就是如下解法递推式很好理解初始化意思是当一个串为0长度时需要操作另一个字符串长度次也就是直接赋予下标编辑距离dp[i-1][j-1]+1意......
  • 代码随想录算法训练营第二十六天| 39. 组合总和 40.组合总和II 131.分割回文串
    组合总和题目链接:39.组合总和-力扣(LeetCode)思路:依然一是套用回溯模板,但是我们这里用回溯的是i而不是i+1,因为元素可以重复使用,注意for循环里if(sum(path)<=target)的等号不能少。classSolution{public:vector<int>path;vector<vector<int>>result;intsu......
  • 代码随想录:数组
    二分查找二分查找是对数组中的区间进行查找。有两种写法:一种是在闭区间内进行查找,另一种是在左闭右开区间内进行查找。每次查找的时候只有按照这个方法就不会出错。二分查找写法一:classSolution{public:intsearch(vector<int>&nums,inttarget){intle......
  • day41 动态规划part3 代码随想录算法训练营 96. 不同的二叉搜索树
    题目:96.不同的二叉搜索树我的感悟:这题,考的概率不大,听一遍,过一遍就行。理解难点:二叉搜索树定义为什么是累加的听课笔记:代码示例:classSolution:defnumTrees(self,n:int)->int:dp=[0]*(n+1)#创建一个长度为n+1的数组,初始化为0d......
  • day40 动态规划part3 代码随想录算法训练营 343. 整数拆分
    题目:343.整数拆分我的感悟:题目很难,但我动力十足!!理解难点:如何拆分为什么要保留dp[i]听课笔记:代码示例:classSolution:defintegerBreak(self,n:int)->int:#思路:#dp[i]是到目前为止能拆分取的最大值#dp[i]可以拆成j*(集合)......
  • 代码随想录 day58 判断子序列 不同的子序列
    判断子序列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子序列中......
  • 代码随想录算法训练营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遍历用法错误,正确写......