🚩传送门：https://leetcode-cn.com/problems/target-sum/

题目

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

输入：“bbbab” 输出：4

一个可能的最长回文子序列为 “bbbb”。

示例 2:

输入：“cbbd” 输出：2

一个可能的最长回文子序列为 “bb”。

解题思路：动态规划

👉 定义：[LeetCode]Dp516 最长回文子序列 - 图1 表示 [LeetCode]Dp516 最长回文子序列 - 图2 的第 [LeetCode]Dp516 最长回文子序列 - 图3 个字符到第 [LeetCode]Dp516 最长回文子序列 - 图4 个字符组成的子串中，最长的回文序列长度是多少。

状态转移方程：

[LeetCode]Dp516 最长回文子序列 - 图5

注意遍历顺序，[LeetCode]Dp516 最长回文子序列 - 图6 从最后一个字符开始往前遍历，[LeetCode]Dp516 最长回文子序列 - 图7 从 [LeetCode]Dp516 最长回文子序列 - 图8 开始往后遍历

初始化 dp[i][i] = 1 单个字符的最长回文序列是 1

结果 dp[0][n - 1]

方式二代码

  1. class Solution {
  2.     public int longestPalindromeSubseq(String s) {
  3.         int n = s.length();
  4.         int[][] dp = new int[n][n];
  5.         for (int i = n - 1; i >= 0; i--) {
  6.             //1. 单独必然构成回文
  7.             dp[i][i] = 1;
  8.             for (int j = i + 1; j < n; j++) {
  9.                 if (s.charAt(i) == s.charAt(j)) 
  10.                     dp[i][j] = dp[i + 1][j - 1] + 2;     
  11.                 else 
  12.                     dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
  13.             }
  14.         }
  15.         return dp[0][n - 1];
  16.     }
  17. }