品牌网站开发,创新的微商城网站建设,济南城市建设学院网站,深圳画册设计印刷公司题目
https://www.lintcode.com/problem/667/
给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000.样例
样例1输入#xff1a; bbbab
输出#xff1a; 4
解释#xff1a;
一个可能的最长回文序列为 bbbb
样例2输入…题目
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 subsequences 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(LR) return 1;if(L R-1){return str[L] str[R]? 2:1;}int p1 f(str,L1,R-1);int p2 f(str,L,R-1);int p3 f(str,L1,R);int p4 str[L] ! str[R] ? 0:(2f(str,L1,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][i1] str[i] str[i1]?2:1;}for (int i n-3; i 0 ; i--) {for (int j i2; j n ; j) {int p1 dp[i1][j-1];int p2 dp[i][j-1];int p3 dp[i1][j];int p4 str[i]!str[j]?0:(2dp[i1][j-1]);dp[i][j] Math.max(Math.max(p1,p2),Math.max(p3,p4));}}return dp[0][n-1];}
}
