题解 | #编号子回文II#
编号子回文II
https://www.nowcoder.com/practice/62e2d96d7b534d22a9b754005a4138a5
这个问题可以使用动态规划来解决。我们可以定义一个二维数组 dp
,其中 dp[i][j]
表示字符串 s
中从第 i
个字符到第 j
个字符的最长回文子序列的长度。然后我们可以遍历每一个位置,对于每一个位置,我们判断它的两边的字符是否相等,如果相等,那么它就是一个回文子序列。最后,我们遍历一遍 dp
数组,找到最长的回文子序列就是答案。
import java.util.*; public class Solution { 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; for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { 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]; } }
算法题刷刷刷 文章被收录于专栏
数组、链表、栈、队列、堆、树、图等。 查找和排序:二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划:背包问题、最长公共子序列、最短路径 贪心算法:活动选择、霍夫曼编码 图:深度优先搜索、广度优先搜索、拓扑排序、最短路径算法(如 Dijkstra、Floyd-Warshall) 字符串操作:KMP 算法、正则表达式匹配 回溯算法:八皇后问题、0-1 背包问题 分治算法:归并排序、快速排序