开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

用带缓存的递归求解最长回文子序列的大O分析

最长回文子序列是指在一个字符串中，找到一个最长的子序列，使得该子序列从左到右和从右到左读取是一样的。例如，在字符串"abcbda"中，最长回文子序列是"abcba"，长度为5。

带缓存的递归是一种优化技术，用于减少重复计算。在求解最长回文子序列时，可以使用带缓存的递归算法来提高效率。

大O分析是一种衡量算法时间复杂度的方法，用于评估算法的运行时间随输入规模增长的趋势。在求解最长回文子序列的问题中，使用带缓存的递归算法的时间复杂度为O(n^2)，其中n是字符串的长度。

具体的算法步骤如下：

定义一个二维数组dp，其中dp[i][j]表示字符串从第i个字符到第j个字符的最长回文子序列的长度。
初始化dp数组的对角线元素为1，即dp[i][i]=1，表示单个字符本身就是一个回文子序列。
从字符串的最后一个字符开始，逐个向前遍历字符串。
对于每个字符，从当前字符的下一个字符开始，逐个向后遍历字符串。
如果当前字符和遍历到的字符相等，则dp[i][j] = dp[i+1][j-1] + 2，表示当前字符和遍历到的字符可以构成一个更长的回文子序列。
如果当前字符和遍历到的字符不相等，则dp[i][j] = max(dp[i+1][j], dp[i][j-1])，表示当前字符和遍历到的字符无法构成回文子序列，需要从前一个字符或后一个字符中选择较长的回文子序列。
遍历完所有字符后，dp[0][n-1]即为最长回文子序列的长度，其中n为字符串的长度。

带缓存的递归算法通过缓存已经计算过的结果，避免重复计算，从而提高了算法的效率。在求解最长回文子序列时，可以使用一个二维数组cache来缓存已经计算过的dp值。每次计算dp[i][j]时，先检查cache[i][j]是否已经计算过，如果已经计算过，则直接返回缓存的结果，否则按照上述步骤计算dp[i][j]并将结果存入cache中。

带缓存的递归算法的时间复杂度为O(n^2)，空间复杂度为O(n^2)，其中n是字符串的长度。

推荐的腾讯云相关产品和产品介绍链接地址：

腾讯云云服务器（CVM）：https://cloud.tencent.com/product/cvm
腾讯云云数据库MySQL版：https://cloud.tencent.com/product/cdb_mysql
腾讯云云原生容器服务（TKE）：https://cloud.tencent.com/product/tke
腾讯云CDN加速：https://cloud.tencent.com/product/cdn
腾讯云云安全中心：https://cloud.tencent.com/product/ssc
腾讯云音视频处理（MPS）：https://cloud.tencent.com/product/mps
腾讯云人工智能（AI）：https://cloud.tencent.com/product/ai
腾讯云物联网（IoT）：https://cloud.tencent.com/product/iotexplorer
腾讯云移动开发平台（MTP）：https://cloud.tencent.com/product/mtp
腾讯云对象存储（COS）：https://cloud.tencent.com/product/cos
腾讯云区块链服务（BCS）：https://cloud.tencent.com/product/bcs
腾讯云元宇宙（Tencent XR）：https://cloud.tencent.com/product/xr

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

『ACM-算法-动态规划』初识DP动态规划算法

二、能采用动态规划求解的问题的一般要具有3个性质：最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。...上一章用的是递归的做法，这次我们采用递推的做法。递归：从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为递归。...，上文讲到的最长单调子序列就是经典的线性模型，这里的线性指的是状态的排布是性的。...这样做的时间复杂度降为O(Vsum(logMi) )。找不到出处了给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。...本题可转化为动态规划算法求解最长公共子序列问题，然后用总字符串长度减去最长子序列长度，便得出问题的答案。先将给定的初始字符串S1反过来排列，设为S2，求S1和S2的最长公共子序列便可。

6492 0

字节跳动的一道动态规划面试题

正好我们昨天在聊动态规划的爬楼梯问题，今天我们也就来聊聊字节面试题中的最长回文子序列问题。题目是这样的：给定一个序列，找到其中最长的回文子序列，并返回该序列的长度。...示例 1: 输入: "abdbca" 输出: 5 一个可能的最长回文子序列为 "abdba"。示例 2: 输入: "cddpd" 输出: 3 一个可能的最长回文子序列为 "ddd"。...时间复杂度达到了Ｏ(2^n)，ｎ是输入序列的长度，这里的空间复杂度是O(n)。没关系，我们再来用我们擅长的缓存来优化。自上而下我们来用一个数组去保存已经解决过的子问题。...我们现在用一个二维数组缓存了子问题的结果，dp[st.length()][st.length()]，也就是说，我们不会有超过n*n的子问题，n是输入序列的长度，这意味着我们的时间复杂度是O(n^2)。...而我们的空间复杂度也因为数组的开销变成了O(n^2)，没关系，空间换时间嘛，很正常。自下而上我们是想尝试给定序列的所有子序列，我们还是用二维数组来存储我们的结果。

1K1 0

动态规划(dynamic programming)

状态转移方程的定义和我们是如何定义子问题的有关比如：求最长连续回文串: 给出一个字符串S，求最长的连续回文串，例如串 babcbabcbaccba 最长回文是:abcbabcba 我们如果定义...p( i ) ：以i结尾的最长回文串我们会发现我们用子问题无法表示出p(i+1) 我们重新考虑一下原问题最长连续回文串如果用另一种方式来重新定义这个问题已知字符串 S[0,n] 求回文传...动态规划与贪心等其他算法的比较动态规划与分治，减治分治：将大问题分成若干个小问题去解决递归的求解每个小问题，每个小问题之间没有关系例如快排减治：将大问题缩减成小问题...而贪心算法任务无需求解所有子问题，所以选择在当前情况下最优的情况自顶向下的求解问题，贪心可以认为是动态规划的一个特例如果用一个树来表示子问题的话可以认为动态规划考虑了树中的所有节点而贪心算法减去了树了许多枝干...，在考虑了通向最优解的那一条路常见的可以用动态规划解决的问题 1、最大连续子序列和：给定k个整数的序列{N1,N2,...

1.4K5 0

看一遍就理解：动态规划详解

我们先来看看这个递归的时间复杂度吧：递归时间复杂度 = 解决一个子问题时间*子问题个数一个子问题时间 = f（n-1）+f（n-2），也就是一个加法的操作，所以复杂度是 O(1)；问题个数 =...所以呢，用了备忘录递归算法，递归树变成光秃秃的树干咯，如下：带备忘录的递归算法，子问题个数=树节点数=n，解决一个子问题还是O(1),所以带备忘录的递归算法的时间复杂度是O(n)。...接下来呢，我们用带备忘录的递归算法去撸代码，解决这个青蛙跳阶问题的超时问题咯~，代码如下： public class Solution { //使用哈希map，充当备忘录的作用 Map<...但是呢：带备忘录的递归，是从f(10)往f(1）方向延伸求解的，所以也称为自顶向下的解法。...哈哈，想到这，我们就可以用dp[i]表示以num[i]这个数结尾的最长递增子序列的长度啦，然后再来看看其中的规律：其实，nums[i]结尾的自增子序列，只要找到比nums[i]小的子序列，加上nums

4K8 0

看一遍就理解：动态规划详解

所以呢，用了备忘录递归算法，递归树变成光秃秃的树干咯，如下： ? 带备忘录的递归算法，子问题个数=树节点数=n，解决一个子问题还是O(1),所以带备忘录的递归算法的时间复杂度是O(n)。...接下来呢，我们用带备忘录的递归算法去撸代码，解决这个青蛙跳阶问题的超时问题咯~，代码如下： public class Solution { //使用哈希map，充当备忘录的作用 Map<...其实，还可以用动态规划解决这道题。自底向上的动态规划动态规划跟带备忘录的递归解法基本思想是一致的，都是减少重复计算，时间复杂度也都是差不多。...但是呢：带备忘录的递归，是从f(10)往f(1）方向延伸求解的，所以也称为自顶向下的解法。...带备忘录的递归解法，空间复杂度是O(n)，但是呢，仔细观察上图，可以发现，f（n）只依赖前面两个数，所以只需要两个变量a和b来存储，就可以满足需求了，因此空间复杂度是O(1)就可以啦 ?

5883 0

看一遍就理解：动态规划详解

所以呢，用了备忘录递归算法，递归树变成光秃秃的树干咯，如下： ? 带备忘录的递归算法，子问题个数=树节点数=n，解决一个子问题还是O(1),所以带备忘录的递归算法的时间复杂度是O(n)。...接下来呢，我们用带备忘录的递归算法去撸代码，解决这个青蛙跳阶问题的超时问题咯~，代码如下： public class Solution { //使用哈希map，充当备忘录的作用 Map<Integer...其实，还可以用动态规划解决这道题。自底向上的动态规划动态规划跟带备忘录的递归解法基本思想是一致的，都是减少重复计算，时间复杂度也都是差不多。...但是呢：带备忘录的递归，是从f(10)往f(1）方向延伸求解的，所以也称为自顶向下的解法。...带备忘录的递归解法，空间复杂度是O(n)，但是呢，仔细观察上图，可以发现，f（n）只依赖前面两个数，所以只需要两个变量a和b来存储，就可以满足需求了，因此空间复杂度是O(1)就可以啦 ?

34.4K51 42

盘点互联网公司最常见的面试编程题

常用的一些算法思想或类别： 1) 动态规划，常考，重要的是找到初始条件，状态迭代方程，比如机器人不同的行走路线个数等；还有背包问题、最长子序列等等，题目相当灵活； 2) 字符串：判断是否为回文字符串，子串...，共有子串等； 3) 数字考察，比如求sqrt(2)，判断数字是否为幸福数等； 4) 二分查找：sqrt(2)求法，使用它的前提一般是要求数组有序； 5) 深度优先搜索：一般可结合回溯求解很多有意思的问题...两个数组的交集II 334. 递增的三元字序列 240. 搜索二维矩阵II 238. 除自身以外数组的乘积链表 138.复制带随机指针的链表 141. 环形链表 148. 排序链表 160....计算右侧小于当前元素的个数滑动窗口 395. 至少有K个重复字符的最长子串动态规划 124. 二叉树中的最大路径和 128. 最长连续序列 198. 打家劫舍 279. 完全平方数 300....最长上升子序列 322. 零钱兑换 329. 矩阵中的最长递增路径图论 127. 单词接龙 200. 岛屿的个数 207. 课程表 210. 课程表II 字符串 125. 验证回文串 131.

2.6K2 0

盘点互联网公司最常见的面试编程题

常用的一些算法思想或类别： 1) 动态规划，常考，重要的是找到初始条件，状态迭代方程，比如机器人不同的行走路线个数等；还有背包问题、最长子序列等等，题目相当灵活； 2) 字符串：判断是否为回文字符串，子串...，共有子串等； 3) 数字考察，比如求sqrt(2)，判断数字是否为幸福数等； 4) 二分查找：sqrt(2)求法，使用它的前提一般是要求数组有序； 5) 深度优先搜索：一般可结合回溯求解很多有意思的问题...两个数组的交集II 334. 递增的三元字序列 240. 搜索二维矩阵II 238. 除自身以外数组的乘积链表 138.复制带随机指针的链表 141. 环形链表 148. 排序链表 160....计算右侧小于当前元素的个数滑动窗口 395. 至少有K个重复字符的最长子串动态规划 124. 二叉树中的最大路径和 128. 最长连续序列 198. 打家劫舍 279. 完全平方数 300....最长上升子序列 322. 零钱兑换 329. 矩阵中的最长递增路径图论 127. 单词接龙 200. 岛屿的个数 207. 课程表 210. 课程表II 字符串 125. 验证回文串 131.

1K2 0

盘点互联网公司最常见的面试编程题

常用的一些算法思想或类别： 1) 动态规划，常考，重要的是找到初始条件，状态迭代方程，比如机器人不同的行走路线个数等；还有背包问题、最长子序列等等，题目相当灵活； 2) 字符串：判断是否为回文字符串，子串...，共有子串等； 3) 数字考察，比如求sqrt(2)，判断数字是否为幸福数等； 4) 二分查找：sqrt(2)求法，使用它的前提一般是要求数组有序； 5) 深度优先搜索：一般可结合回溯求解很多有意思的问题...两个数组的交集II 334. 递增的三元字序列 240. 搜索二维矩阵II 238. 除自身以外数组的乘积链表 138.复制带随机指针的链表 141. 环形链表 148. 排序链表 160....计算右侧小于当前元素的个数滑动窗口 395. 至少有K个重复字符的最长子串动态规划 124. 二叉树中的最大路径和 128. 最长连续序列 198. 打家劫舍 279. 完全平方数 300....最长上升子序列 322. 零钱兑换 329. 矩阵中的最长递增路径图论 127. 单词接龙 200. 岛屿的个数 207. 课程表 210. 课程表II 字符串 125. 验证回文串 131.

8842 0

动态规划之最长回文子串

大家好，又见面了，我是你们的朋友全栈君。问题：给出一个字符串S，求S的最长回文子串的长度。...样例字符串"PATZJUJZTACCBCC"的最长回文子串为"ATZJUJZTA",长度为9。还是先看暴力解法:枚举子串的两个端点i和j,判断在[i, j]区间内的子串是否回文。...从复杂度上来看，枚举端点需要0(n2),判断回文需要0(n)，因此总复杂度是O(n3)。终于碰到一个暴力复杂度不是指数级别的问题了!但是O(n)的复杂度在n很大的情况依旧不够看。...可能会有读者想把这个问题转换为最长公共子序列(LCS) 问题来求解:把字符串S倒过来变成字符串T,然后对S和T进行LCS模型求解，得到的结果就是需要的答案。...例如字符串S= “ABCDZJUDCBA”,将其倒过来之后会变成T = “ABCDUJZDCBA”,这样得到最长公共子串为”ABCD”，长度为4,而事实上S的最长回文子串长度为1。

4545 0

浅谈我对动态规划的一点理解---大家准备好小板凳，我要开始吹牛皮了~~~

因此，求解LCS的问题则变成递归求解的两个子问题。但是，上述的递归求解的办法中，重复的子问题多，效率低下。改进的办法——用空间换时间，用数组保存中间状态，方便后面的计算。...举个例子，给出一序列，求出该序列的最长上升子序列的最大长度。我们可以这么考虑，用数组a[]存储序列，b[i]表示以a[i]为结尾的序列的最大长度。...举个例子，我们要在一个字符串中要到最长的回文子串。暴力求解：最容易想到的就是暴力破解，求出每一个子串，之后判断是不是回文，找到最长的那个。...这样最长回文子串就能分解成一系列子问题了。这样需要额外的空间O(N^2)，算法复杂度也是O(N^2)。首先定义状态方程和转移方程： P[i,j]=0表示子串[i,j]不是回文串。...分析蓝色部分 ? 如果存在最长公共前后缀的话，比如这样： ? 就可以在下次匹配的时候用，这样避免了i的回溯 ?

4.6K8 1

LeetCode(4-寻找两个正序数组的中位数&&5-最长回文子串&&6-Z形变换)

目录 - 寻找两个正序数组的中位数 - !!!最长回文子串!!!...(重点掌握) ~暴力求解 ~动态规划 ~中心扩散法 - Z形变换寻找两个正序数组的中位数题目描述: 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。...最长回文子串!!!(重点掌握) 题目描述: 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。...示例 2：输入: “cbbd” 输出: “bb” 暴力求解解题思路: 当然了不动脑子的话,很容易想到暴力求解.只需要从最长的字符串开始递归进行检查,看是不是回文串,如果是的话,那么就直接返回即可....这里我们就来分析一下我们怎么能快速的判断一个字符串是不是回文串呢.可以看到这部分我用的是动态规划,所以关于动态规划,大家首先需要考虑的就是找到状态转移方程!!!

4113 0

（粗糙的笔记）动态规划

： O(2^n) 动态规划从蛮力枚举到带备忘递归优化子问题解，避免重复计算构造备忘录P[i,c]，P[i,c]表示在前i个商品中选择，背包容量为c时的最优解输入：商品集合{h,......n\cdot C) 上面带备忘递归和递推求解的方法都属于动态规划：带备忘递归：自顶向下递推求解：自底向上最优子结构性质：问题的最优解由相关子问题最优解组合而成子问题可以独立求解动态规划与分而治之的区别...和 Y[1..j] 的最长公共子序列长度递推关系建立：分析最优子结构考察末尾字符：情况1： x_i\neq y_j 时， C[i,j]=max\{ C[i,j-1],C[i-1,j] \} 情况...n\cdot m) 最长公共子串子串：给定序列中零个或多个连续的元素组成的子序列蛮力枚举序列X和序列Y各选择一个位置依次检查元素是否匹配：元素相等则继续匹配元素不等或某序列已达端点...动态规划问题结构分析：给出问题表示： C[i,j] 表示 X[1..i] 和 Y[1..j] 中，以 x_i 和 y_j 结尾的最长公共子串 Z[1..l] 的长度递推关系建立：分析最优子结构

2644 0

高频经典算法题汇总

复制带随机指针的链表 di[node] = Node, key为原节点，val为新节点, di[node].next = di.get(node.next), O(2n) 21...最长回文子串 - M dp[i][j], dp[0][0]=1, 要for r再for l以确保dp[...最长公共子序列 - M dp[i+1][]j+1], dp = (max(dp[i-1][j], dp[i][j-1])...填充每个节点的下一个右侧节点指针对于任意一次递归，只需要考虑如何设置子节点的 next 属性 117....最长上升子序列 dp[n], if nums[i] > nums[j]: dp[i] = max(dp[i

2.4K6 0

Python实现常见的回文字符串算法

]: return False left += 1 right -= 1 return True 当然还有切片string[::-1] 最长的回文子串...n) 时间复杂度：尽管内层存在循环，但是内层循环只对尚未匹配的部分进行，对于每一个字符来说，只会进行一次，所以时间复杂度是 O(n) 最长回文前缀所谓前缀，就是以第一个字符开始下面的最长回文前缀 abbabbc...def solution(s): length = longest_palindrome_prefix(s) return s[length:][::-1] + s 最长回文子序列动态规划法...dp[i][j] 表示子序列 s[i..j] 中存在的最长回文子序列长度初始化dp[i][i] = 1 当 s[i] == s[j] 为 true 时，dp[i][j] = dp[i+1][j -...1] + 2 当 s[i] == s[j] 为 false 时，dp[i][j] = max(dp[i+1][j], dp[i][j - 1]) # 求得最长回文子序列的长度 def solution(

2.2K4 0

C++ 动态规划经典案例解析之最长公共子序列（LCS）_窥探递归和动态规划的一致性

前言动态规划处理字符相关案例中，求最长公共子序列以及求最短编辑距离，算是经典中的经典案例。讲解此类问题的算法在网上一抓应用一大把，即便如此，还是忍不住有写此文的想法。...最长公共子序列(LCS) 2.1 问题描述最长公共子序列，指找出 2 个或多个字符串中的最长公共子序列。如字符串 s1=kabc和s2=taijc，其最长公共子序列是ac。...无论由上向下，还是由下向上，其本质都是知道子问题答案后，再求解出大问题的答案。动态规划算法是直接了当，递归是迂回求解。现以求字符串的最长公共子序列为例，讲解动态规划的求解过程。...构建dp数组，用来记录所有子问题的解，类似于递归实现的缓存器。...总结最长公共子序列很有代表性，分析基于递归和动态规划的实现过程，可以帮助我们理解此类问题，且解决此类问题。

5262 0

最长回文子串（Longest Palindromic Substring）——三种时间复杂度的解法「建议收藏」

子串：小于等于原字符串长度由原字符串中任意个连续字符组成的子序列回文：关于中间字符对称的文法，即“aba”(单核)、“cabbac”(双核)等最长回文子串：1.寻找回文子串；2.该子串是回文子串中长度最长的...一、O(n^3)时间复杂度方法——暴力求解 1.思想： 1）从最长的子串开始，遍历所有该原字符串的子串； 2）每找出一个字符串，就判断该字符串是否为回文； 3）子串为回文时，则找到了最长的回文子串...后者大时，将最长的回文子串改为low与high之间的； 4）重复执行2）、3），直至high-low+1 等于原字符串长度或者遍历到最后一个字符，取当前截取到的回文子串，该子串即为最长的回文子串...2.时间复杂度解释：遍历字符：一层循环、O(n-1)；找以当前字符为中心的最长回文子串：嵌套两个独立循环、O(2n*(n-1)) = O(n^2)。...3）Len数组求解（线性复杂度（O(n)））： a.遍历S_new数组，i为当前遍历到的位置，即求解以S_new[i]为中心的最长回文子串的Len[i]; b.设置两个参数：

9411 0

LeetCode(4-寻找两个正序数组的中位数&&5-最长回文子串&&6-Z形变换)

目录寻找两个正序数组的中位数 !!!最长回文子串!!!...(重点掌握) 暴力求解动态规划中心扩散法 Z形变换寻找两个正序数组的中位数题目描述: 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。...最长回文子串!!!(重点掌握) 题目描述: 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。...示例 2：输入: “cbbd” 输出: “bb” 暴力求解解题思路: 当然了不动脑子的话,很容易想到暴力求解.只需要从最长的字符串开始递归进行检查,看是不是回文串,如果是的话,那么就直接返回即可...这里我们就来分析一下我们怎么能快速的判断一个字符串是不是回文串呢.可以看到这部分我用的是动态规划,所以关于动态规划,大家首先需要考虑的就是找到状态转移方程!!!

1911 0

动态规划，它来了

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。通俗一点动态规划就是从下往上(从前向后)阶梯型求解数值。那么动态规划和递归有什么区别和联系？...很多时候用动态规划能解决的问题，用递归也能解决不过很多时候效率不高可能会用到记忆化搜索。不太明白? 就拿求解斐波那契额数列来说，如果直接用递归不优化，那么复杂度太多会进行很多重复的计算。...对于最长递增子序列，如果不考虑动态规划的方法，使用暴力枚举其实还是比较麻烦的，因为你不知道遇到比前面元素大的是否要递增。...例如 abceef 和a2b2cee3f的最长公共子串就是cee。公共子串是两个串中最长连续的相同部分。如何分析呢?...不同子序列不同子序列也会出现，并且有些难度，前面这篇不同子序列问题分析讲的大家可以看看。给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

5392 0

动态规划：最长回文子串 & 最长回文子序列

最长回文子串和最长回文子序列（Longest Palindromic Subsequence）是指任意一个字符串，它说包含的长度最长的回文子串和回文子序列。...例如：字符串 “ABCDDCEFA”，它的最长回文子串即 “CDDC”，最长回文子序列即 “ACDDCA”。二、最长回文子串 1....思路首先这类问题通过穷举的办法，判断是否是回文子串并再筛选出最长的，效率是很差的。我们使用动态规划的策略来求解它。...为子串起始坐标，i 为子串终点坐标的子串是否是回文的，由于我们是从子问题依次增大求解的，所以求解 [i ... j] 的问题时，比它规模更小的问题结果都是可以直接使用的了。...思路子序列的问题将比子串更复杂，因为它是可以不连续的，这样如果穷举的话，问题规模将会变得非常大，我们依旧是选择使用动态规划来解决。

6652 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭