1
#yyds干货盘点# 动态规划专题：最长回文子序列
source link: https://blog.51cto.com/u_15488507/5814641
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 动态规划专题：最长回文子序列
精选 原创1.简述：
描述给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。
注：回文序列是指这个序列无论从左读还是从右读都是一样的。
本题中子序列字符串任意位置删除k（len(s)>=k>=0）个字符后留下的子串。
数据范围：字符串长度满足
进阶：空间复杂度 ， 时间复杂度
输入一个字符串
输出描述：输出最长回文子序列
示例1abccsb
分别选取第2、3、4、6位上的字符组成“bccb”子序列是最优解
abcdewa
分别选取第一个和最后一个a，再取中间任意一个字符就是最优解
2.代码实现：
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
char c1 = s.charAt(i);
for (int j = i + 1; j < n; j++) {
char c2 = s.charAt(j);
if (c1 == c2) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
char c1 = s.charAt(i);
for (int j = i + 1; j < n; j++) {
char c2 = s.charAt(j);
if (c1 == c2) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK