如果你觉得这篇题解对你有用,可以点个赞或关注再走呗~
分析
求的是:最长回文子序列不是最长回文子串
子序列是不连续的,子串是连续的。
注:
情况1:左右两个端点均包含其中即f[l+1][r-1]+2
情况2:左端点不包含其中即f[l+1][r](r可取可不取)
情况3:右端点不包含其中即f[l][r-1](l可取可不取)
情况4:左右端点均不包含其中,这种情况包含在情况2、情况3中,不需另取一种情况分析。
ACcode
import java.util.*;
public class Main{
static int N=1010;
static int f[][]=new int[N][N];
public static void main(String []args){
Scanner sc=new Scanner(System.in);
String s=sc.next();
int n=s.length();
for(int len=1;len<=n;len++){//枚举的区间长度
for(int i=0;i+len-1<n;i++){
int j=i+len-1;//区间右端点
if(len==1)f[i][j]=1;//长度是1则只有一个点回文序列为1
else{
if(s.charAt(i)==s.charAt(j))f[i][j]=f[i+1][j-1]+2;
//i+1~j-1区间求回文序列加上左右两个端点
if(f[i+1][j]>f[i][j])f[i][j]=f[i+1][j];
//大于则覆盖掉
if(f[i][j-1]>f[i][j])f[i][j]=f[i][j-1];
//大于则覆盖掉
}
}
}
System.out.println(n-f[0][n-1]);
}
}
Accode
import java.util.*;
public class Main{
static int N=1010;
static int f[][]=new int[N][N];
public static void main(String []args){
Scanner sc=new Scanner(System.in);
String s=sc.next();
int n=s.length();
for(int len=1;len<=n;len++){
for(int i=0;i+len-1<n;i++){
int j=i+len-1;
if(len==1)f[i][j]=1;
else{
f[i][j]=Math.max(f[i][j-1],f[i+1][j]);
if(s.charAt(i)==s.charAt(j))f[i][j]=Math.max(f[i][j],f[i+1][j-1]+2);
}
}
}
System.out.println(n-f[0][n-1]);
}
}