一、题目

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

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

点击查看原题
难度级别： 中等

二、思路

1）动态规划

设立二维数组dp[i][j]为s[i,j]最长的回文子序列，可以得到状态转移方程：
516. 最长回文子序列-每日一题 - 图1
由于该数组只依赖于本行和商议后状态，也可以优化成一维数组，从后向前遍历字符位置为i，令dp[j]为s[i,j]最长的回文子序列

三、代码

1）动态规划

  1. class Solution {
  2.     public int longestPalindromeSubseq(String s) {
  3.         char[] cs = s.toCharArray();
  4.         int[][] dp = new int[cs.length][cs.length];
  5.         for (int i = cs.length - 1; i >= 0; i--) {
  6.             dp[i][i] = 1;
  7.             for (int j = i + 1; j < cs.length; j++) {
  8.                 if (cs[i] == cs[j]) {
  9.                     dp[i][j] = dp[i+1][j-1] + 2;
  10.                 } else {
  11.                     dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
  12.                 }
  13.             }
  14.         }
  15.         return dp[0][cs.length - 1];
  16.     }
  17. }

时间复杂度为O(n^2)，空间复杂度为O(n^2)

  1. class Solution {
  2.     public int longestPalindromeSubseq(String s) {
  3.         char[] cs = s.toCharArray();
  4.         int[] dp = new int[cs.length];
  5.         for (int i = cs.length - 1; i >= 0; i--) {
  6.             int[] temp = dp;
  7.             dp = new int[cs.length];
  8.             dp[i] = 1;
  9.             for (int j = i + 1; j < cs.length; j++) {
  10.                 if (cs[i] == cs[j]) {
  11.                     dp[j] = temp[j-1] + 2;
  12.                 } else {
  13.                     dp[j] = Math.max(temp[j], dp[j-1]);
  14.                 }
  15.             }
  16.         }
  17.         return dp[cs.length - 1];
  18.     }
  19. }

时间复杂度为O(n^2)，空间复杂度为O(n)