当前位置:网站首页>【LeetCode】最长回文子序列(动态规划)
【LeetCode】最长回文子序列(动态规划)
2022-08-03 23:00:00 【小七mod】
一、题目
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
示例 1:
输入:s = "bbbab" 输出:4 解释:一个可能的最长回文子序列为 "bbbb" 。
示例 2:
输入:s = "cbbd" 输出:2 解释:一个可能的最长回文子序列为 "bb" 。
提示:
1 <= s.length <= 1000
s
仅由小写英文字母组成
二、代码
class Solution {
public int longestPalindromeSubseq(String s) {
// 判空
if (s == null || s.length() == 0) {
return 0;
}
// 将字符串转换为字符数组
char[] str = s.toCharArray();
// 创建dp数组
int n = str.length;
int[][] dp = new int [n][n];
// 赋初值,对两个对角线赋初值
dp[n - 1][n - 1] = 1;
for (int i = 0; i < n - 1; i++) {
dp[i][i] = 1;
dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
}
// 按照动态转移方程对dp数组进行复制,沿对角线方向进行复制
for (int i = 2; i < n; i++) {
// 之所以这里用j表示列,是因为列的范围更好控制,因为所有的对角线最后一个节点一定都是最后一列,是固定不变的
for (int j = i; j < n; j++) {
int r = j;
int l = r - i;
// 动态转移方程
dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
if (str[l] == str[r]) {
dp[l][r] = Math.max(dp[l][r], dp[l + 1][r - 1] + 2);
}
}
}
// 返回结果
return dp[0][n - 1];
}
}
三、解题思路
利用动态规划的思路进行解题。利用已经得出的初值来逐渐退出全部可能的结果。
边栏推荐
猜你喜欢
for loop exercises
获国际权威认可 | 云扩科技入选《RPA全球市场格局报告,Q3 2022》
静态文件快速建站
Embedded Systems: Clocks
Zilliz 2023 Fall Campus Recruitment Officially Launched!
【day6】类与对象、封装、构造方法
Live Preview | Build Business Intelligence, Quickly Embrace Financial Digital Transformation
Embedded Systems: GPIO
BMN: Boundary-Matching Network for Temporal Action Proposal Generation阅读笔记
Fluorescein-PEG-CLS,胆固醇-聚乙二醇-荧光素科研试剂
随机推荐
Nine ways to teach you to read the file path in the resources directory
电商秒杀系统
Boss: There are too many systems in the company, can you realize account interoperability?
获国际权威认可 | 云扩科技入选《RPA全球市场格局报告,Q3 2022》
Live Preview | Build Business Intelligence, Quickly Embrace Financial Digital Transformation
Interpretation of ML: A case of global interpretation/local interpretation of EBC model interpretability based on titanic titanic rescued binary prediction data set using interpret
Research status of target detection at home and abroad
栈的压入、弹出序列
Scala基础【正则表达式、框架式开发原则】
P1996 约瑟夫问题
Quickly build a website with static files
utlis 线程池
剑指offer第22题-链表中倒数第K个节点
pikachu Over permission
数据分析知识点搜集(纯粹的搜集)
Embedded Systems: GPIO
MiniAPI of .NET6 (14): Cross-domain CORS (Part 1)
UVa 1025 - A Spy in the Metro (White Book)
ML's yellowbrick: A case of interpretability (threshold map) for LoR logistic regression model using yellowbrick based on whether Titanic was rescued or not based on the two-class prediction dataset
Kotlin - 扩展函数和运算符重载