题目：
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。 示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。 示例 2: 输入: "cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。 提示： 1 <= s.length <= 1000 s 只包含小写英文字母题意解释
最长子序列区别于最长回文子串，子串必须是连续的，而子序列则可以跳跃， 例如：aabcaa的最长回文子串为aa，但是它的最长回文子序列为aabaa或aacaa.
一般思路
例如：a 则最长回文子序列为 a bab 则最长回文子序列为 bab bacb 则最长回文子序列为 bab 或 bcb 不难发现规律： 从第一个和最后一个开始比较。如果最后一个和第一个相等。 则result等于以第二个到倒数第二个为新的字符串求最长回文子序列加二。
f(“bacb”) = f(“ac”) + 2
如果不相等则有： f(“bacbe”) = max(f(“bacb”)，f(“acbe”)
依次内推。。。。。。
自己踩过的坑(根据上面的推导)：
public static int longestPalindromeSubseq(String s) { return longestPalindromeSubseq(s.toCharArray(),0,s.length()-1); } public int longestPalindromeSubseq(char[] array,int start, int end) { if (start == end) return 1; if (start > end) return 0; if (array[start] == array[end]){ return longestPalindromeSubseq(array,start + 1, end - 1) + 2; }else { return Math.max(longestPalindromeSubseq(array,start, end - 1), longestPalindromeSubseq(array,start + 1, end)); } }运行结果
超出时间限制
分析原因
例如：在计算f(“bacbe”) = max(f(“bacb”)，f(“acbe”)时。当我们计算f(“bacb”) 和f(“acbe”)我们会重复计算f(“ac”) 当字符串越长我们重复计算的次数越多， 这就是我们超时的原因。
优化
如果我们能将我们已经结算过的值保持起来，当再次使用时直接取值即可。
优化后
public static int longestPalindromeSubseq1(String s) { int[][] array = new int[s.length()][s.length()]; return longestPalindromeSubseq(s,0,s.length()-1, array); } private static int longestPalindromeSubseq(String s,int start, int end, int[][] array) { if (array[start][end] != 0) return array[start][end];//如果值已经计算出，则直接返回 if (start == end) return 1;//如果相等则说明只有一个字符了，返回1 if (start > end) return 0;//如果start大于end,返回0 if (s.charAt(start) == s.charAt(end)){ array[start][end] = longestPalindromeSubseq(s,start + 1, end - 1, array) + 2;//保持值 }else { array[start][end] = Math.max(longestPalindromeSubseq(s,start, end - 1, array), longestPalindromeSubseq(s,start + 1, end, array));//保持值 } return array[start][end]; }以上是自己的代码结合相关文章进行改进的，目的是给出一般的思维及其优化过程。
改进（运用动态规划）
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递 推（或者说分治）的方式去解决。动态规划算法的基本思想与分治法类似，也是将待 求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为 后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解 ，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题 ，最后一个子问题就是初始问题的解。
基本思想: 由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子 问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
定义dp数组：dp[i][j]表示区间[i,j]对应子串的最长回文子序列的长度。根据递归式，我们很容易得到状态转移方程： 由于计算dp[i][j]可能需要借助dp[i][j-1]和dp[i+1][j]，即前一列和下一行的结果，所以填表的方向是从下往上，从左往右，如图箭头所示。 代码 public static 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]; }