- 给定一个序列/ 字符串，进行一些操作
- 最后一步将序列/字符串去头/去尾
- 剩下的会是一个区间[I,j]
- 状态自然定义为f[i][j], 表示面对子序列[I…j] 时的最优性质
-
667. 最长的回文序列
-
中文English
-
给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000.
-
Example
-
样例1
-
输入： "bbbab"
-
输出： 4
-
解释：
-
一个可能的最长回文序列为 "bbbb"
-
样例2
-
输入： "bbbbb"
-
输出： 5
|
public class Solution { /** * @param s: the maximum length of s is 1000 * @return: the longest palindromic subsequence's length */ public int longestPalindromeSubseq(String s) { // write your code here char[] ch = s.toCharArray(); if(ch.length==0) { return 0; } int[][]dp = new int[ch.length][ch.length]; int i,j; for(i=0;i<ch.length;++i) { dp[i][i] = 1; } for(i=0;i<ch.length-1;++i) { dp[i][i+1] = ( (ch[i]==ch[i+1])? 2:1); } int len; for(len=3;len<=ch.length;++len) { //0----len n-len ----len for(i=0;i<=ch.length-len;++i) { j = i+len-1; dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]); if(ch[i]==ch[j]) { dp[i][j] = Math.max(dp[i][j],dp[i+1][j-1]+2); } } } return dp[0][ch.length-1]; } } |
使用记忆化搜索
|
public class Solution { /** * @param s: the maximum length of s is 1000 * @return: the longest palindromic subsequence's length */ public int longestPalindromeSubseq(String s) { // write your code here ch = s.toCharArray(); int n = ch.length; if(n<=1) return n; dp = new int[n][n]; int i,j; for(i=0;i<n;++i) { for(j=i;j<n;++j) { dp[i][j] = -1; } } dfs(0,n-1); return dp[0][n-1]; } char[]ch = null; int[][]dp = null; public void dfs(int i,int j) { if(dp[i][j] != -1) return; if(i==j) { dp[i][j] = 1; return; } if(i+1==j) { dp[i][j] = (ch[i]==ch[j]) ? 2:1; return; } dfs(i,j-1); dfs(i+1,j); dfs(i+1,j-1); dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]); if(ch[i]==ch[j]) { dp[i][j] = Math.max(dp[i][j],dp[i+1][j-1]+2); } } } |