|
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); } }
} |
原文：https://www.cnblogs.com/lyr-2000/p/13061730.html