文章目录
- 一、真题链接
- 二、如何解决
- 2.1算法思路
- 2.2 算法步骤
- 2.3 Java算法实现
一、真题链接
还好我以前刷过这道题，
其实题目就是LeetCode的 516.最长回文子序列，
地址：https://leetcode.cn/problems/longest-palindromic-subsequence/description/
子序列定义为:不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
-
示例 1:
- 输入：s = “bbbab”
- 输出：4
- 解释：一个可能的最长回文子序列为"bbbb"
-
示例 2:
- 输入：S = “cbbd”
- 输出：
- 解释：一个可能的最长回文子序列为"bb"
-
提示:
- 1 <= s.length <= 1000。
- s仅由小写英文字母组成
二、如何解决
为了找到一个给定字符串的最长回文子序列及其长度，我们可以使用动态规划（DP）算法。下面是详细的算法步骤和Java实现：
2.1算法思路
作者：labuladong
链接：https://leetcode.cn/problems/longest-palindromic-subsequence/solutions/67456/zi-xu-lie-wen-ti-tong-yong-si-lu-zui-chang-hui-wen/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
定义一个二维dp数组
int n = arr.length;
int[][] dp = new dp[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (arr[i] == arr[j]) dp[i][j] = dp[i][j] + ...elsedp[i][j] = 最值(...)}
}
找状态转移需要归纳思维，说白了就是如何从已知的结果推出未知的部分，这样定义容易归纳，容易发现状态转移关系。
具体来说，如果我们想求 dp[i][j]，假设你知道了子问题 dp[i+1][j-1] 的结果（s[i+1..j-1] 中最长回文子序列的长度），你是否能想办法算出 dp[i][j] 的值（s[i..j] 中，最长回文子序列的长度）呢？
可以！这取决于 s[i] 和 s[j] 的字符：
如果它俩相等，那么它俩加上 s[i+1..j-1] 中的最长回文子序列就是 s[i..j] 的最长回文子序列：
如果它俩不相等，说明它俩不可能同时出现在 s[i..j] 的最长回文子序列中，那么把它俩分别加入 s[i+1..j-1] 中，看看哪个子串产生的回文子序列更长即可：
以上两种情况写成代码就是这样：
if (s[i] == s[j])// 它俩一定在最长回文子序列中dp[i][j] = dp[i + 1][j - 1] + 2;
else// s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
至此，状态转移方程就写出来了，根据 dp 数组的定义，我们要求的就是 dp[0][n - 1]，也就是整个 s 的最长回文子序列的长度。
2.2 算法步骤
-
定义DP数组：设
dp[i][j]表示字符串s[i...j]的最长回文子序列的长度。 -
初始化：
- 对于每个单字符子串，
dp[i][i] = 1，因为单个字符本身就是回文子序列。
- 对于每个单字符子串，
-
状态转移：
- 如果
s[i] == s[j]，那么dp[i][j] = dp[i + 1][j - 1] + 2。 - 如果
s[i] != s[j]，那么dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。
- 如果
-
边界条件：从小到大填表，确保所有子问题都已解决。
-
回溯找到最长回文子序列：
- 从
dp[0][n-1]开始，回溯字符串，找到对应的最长回文子序列。
- 从
2.3 Java算法实现
首先明确一下 base case，如果只有一个字符，显然最长回文子序列长度是 1，也就是 dp[i][j] = 1 (i == j)。
因为 i 肯定小于等于 j，所以对于那些 i > j 的位置，根本不存在什么子序列，应该初始化为 0。
另外，看看刚才写的状态转移方程，想求 dp[i][j] 需要知道 dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1] 这三个位置；再看看我们确定的 base case，填入 dp 数组之后是这样：
为了保证每次计算 dp[i][j]，左下右方向的位置已经被计算出来，只能斜着遍历或者反着遍历：
public class LongestPalindromicSubsequence {public static void main(String[] args) {// 测试字符串String s = "bbabcbcab";// 调用方法找到最长回文子序列及其长度Result result = findLongestPalindromicSubsequence(s);// 输出结果System.out.println("最长回文子序列的长度是：" + result.length);System.out.println("最长回文子序列是：" + result.subsequence);}/*** 查找字符串s的最长回文子序列及其长度* @param s 给定的字符串* @return 包含最长回文子序列及其长度的Result对象*/public static Result findLongestPalindromicSubsequence(String s) {int n = s.length();if (n == 0) return new Result(0, "");// 将字符串转换为字符数组，可以避免多次调用 String.charAt 方法，从而提高性能char[] charArray = s.toCharArray();// dp数组，dp[i][j]表示字符串charArray[i...j]的最长回文子序列的长度int[][] dp = new int[n][n];// 初始化：每个单字符子串的回文长度为1for (int i = 0; i < n; i++) {dp[i][i] = 1;}// 填充DP数组// len表示当前考虑的子串长度，从2开始，一直到字符串的总长度for (int len = 2; len <= n; len++) {// i和j分别表示子串的起始和结束位置for (int i = 0; i < n - len + 1; i++) {int j = i + len - 1;if (charArray[i] == charArray[j]) {// 如果两端字符相等，则最长回文子序列长度+2// 表示去掉两端字符后的最长回文子序列长度加上这两个字符的长度。dp[i][j] = dp[i + 1][j - 1] + 2;} else {// 否则，取去掉左端或右端字符后的较大值dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}// 回溯构建最长回文子序列：通过双指针和DP数组，回溯构建最长回文子序列。StringBuilder subsequence = new StringBuilder();// 使用双指针 i 和 j，从字符串的两端向中间移动。int i = 0, j = n - 1;while (i <= j) {if (charArray[i] == charArray[j]) {// 如果两端字符相等，加入到回文子序列中subsequence.append(charArray[i]);// 并同时移动 i 和 ji++;j--;} else if (dp[i + 1][j] > dp[i][j - 1]) {// 如果去掉左端字符后的子序列更长，向右移动i++;} else {// 否则，向左移动j--;}}// 构建完整的回文子序列：通过反转构建的回文子序列并拼接得到最终结果。// 将构建的回文子序列 subsequence 反转得到 reverseSubsequenceStringBuilder reverseSubsequence = new StringBuilder(subsequence).reverse();if (subsequence.length() > 1) {// 如果回文子序列长度大于1，拼接中间部分，形成完整的回文子序列subsequence.append(reverseSubsequence.substring(1));} else {// 否则，直接拼接整个反转后的部分reverseSubsequencesubsequence.append(reverseSubsequence);}// 返回结果对象，包含最长回文子序列长度及其内容return new Result(dp[0][n - 1], subsequence.toString());}// 内部类，保存最长回文子序列及其长度static class Result {// 长度int length;// 最长回文子序列String subsequence;Result(int length, String subsequence) {this.length = length;this.subsequence = subsequence;}}
}
