lintcode 667 · 最长的回文序列【中等 递归到动态规划】

题目

https://www.lintcode.com/problem/667/

给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000.样例
样例1输入： "bbbab"
输出： 4
解释：
一个可能的最长回文序列为 "bbbb"
样例2输入： "bbbbb"
输出： 5

思路

	思路1：运用最长公共子序列的方法来做，假设求字符串s1的最长回文子序列，我们先把s1反转得到字符串s2,求的s1和s2的最长公共子序列就是答案思路2： 看下面的答案

参考代码

public class Solution {/*** @param s: the maximum length of s is 1000* @return: the longest palindromic subsequence's length*/public int longestPalindromeSubseq(String s) {if(s ==null || s.length() ==0) return 0;char[] str = s.toCharArray();//return f(str,0,str.length-1); //递归，超时return f2(str); //动态规划1,可以通过}public static int f(char[] str,int L,int R){if(L==R) return 1;if(L== R-1){return str[L] == str[R]? 2:1;}int p1 = f(str,L+1,R-1);int p2 = f(str,L,R-1);int p3 = f(str,L+1,R);int p4 = str[L] != str[R] ? 0:(2+f(str,L+1,R-1));int ans = Math.max(Math.max(p1,p2),Math.max(p3,p4));return ans;}public static int f2(char[] str){int n = str.length;int[][] dp = new int[n][n];dp[n-1][n-1]=1;for (int i = 0; i <n-1 ; i++) {dp[i][i] =1;dp[i][i+1] = str[i] == str[i+1]?2:1;}for (int i = n-3; i >=0 ; i--) {for (int j = i+2; j <n ; j++) {int p1 = dp[i+1][j-1];int p2 = dp[i][j-1];int p3 = dp[i+1][j];int p4 = str[i]!=str[j]?0:(2+dp[i+1][j-1]);dp[i][j] =Math.max(Math.max(p1,p2),Math.max(p3,p4));}}return dp[0][n-1];}
}