【LeetCode】最长回文子序列
2023-09-14 09:13:24 时间
先上代码:
代码
#coding=utf-8
# 本题为考试单行多行输入输出规范示例,无需提交,不计分。
def solve():
s = input()
leng = len(s)
dp = [[0 for i in range(leng)] for i in range(leng)]
# print(dp)
for i in reversed(range(leng)):
dp[i][i] = 1
for j in range(i+1,leng):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j],dp[i][j-1])
return dp[0][leng-1]
res = solve()
print(res)
题目比较简单,但是得保持题感才行。这是今天喜马拉雅的笔试中的编程题(搜索推荐算法)。
思想
设 dp[i][j]
表示为从i到j的序列的最长回文子序列,需要注意一下遍历的方向是从后往前,也就是如下矩阵的上三角部分:
如果对于一个长度为5的字符串,那么遍历的区间就是 [5,5]
=> [4,5]
=> [3,5]
… => [0,5]
递推公式比较简单,参考代码即可。
相关文章
- [LeetCode] Binary Tree Level Order Traversal 二叉树层次遍历(DFS | BFS)
- Java实现LeetCode 5450. 满足条件的子序列数目(双指针)
- Java实现 LeetCode 761 特殊的二进制序列(括号问题)
- Java实现 LeetCode 673 最长递增子序列的个数(递推)
- Java实现 LeetCode 659 分割数组为连续子序列 (哈希)
- Java实现 LeetCode 376 摆动序列
- Java实现 LeetCode 300 最长上升子序列
- Java实现 LeetCode 128 最长连续序列
- Java实现 LeetCode 105 从前序与中序遍历序列构造二叉树
- 【哈希表】leetcode 128. 最长连续序列【中等】
- LeetCode-891. 子序列宽度之和【排序,数学,数组】
- leetcode 106. 从中序与后序遍历序列构造二叉树
- LeetCode -- 最大连续乘积子序列
- 【LeetCode Python实现】673. 最长递增子序列的个数(中等)
- leetcode 300. 最长递增子序列 js 动态规划实现
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
- 【Leetcode刷题Python】1143. 最长公共子序列