algorithm - 选择一对不重叠的回文子串的方法数

Question

给定一个字符串s，期望找到选择一对不重叠的回文子串的方法的数量。
例如在字符串 abcdcefdfdio 中，一种方法是选择 cdc 和 dfd。
我的方法是 dp 方法:

    String s = sc.next();
    int n = s.length();
    int firstsum[] = new int[n];//firstsum[i] stores the number of palindromes in the substring (0...i)
    int[][] A = new int[n][n];//A[i][j]=1 denotes the substring (i...j) is a palindrome and =0 otherwise
    for(int i=0;i<n;++i)
    {
        firstsum[i]=0;
        for(int j=i;j<n;++j)
        {
            if(check(s.substring(i,j+1))==1)
            {
                A[i][j]=1;
            }
            else
                A[i][j]=0;
        }
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<=i;++j)
        {
            if(A[j][i]==1)
                firstsum[i]++;
        }
        if(i>0)
            firstsum[i]+=firstsum[i-1];
    }
    int cnt=0;
    for(int i=1;i<n;++i)
    {
        for(int j=i;j<n;++j)
            cnt+=A[i][j]*firstsum[i-1];
    }
    System.out.print(cnt);//answer

solution正在工作但超过了时间限制。有没有更好的方法，最好是在 DP 中？

Answer 1

删除 A[i][j] 填充循环。在最坏的情况下为 O(n^3)。

试试这段代码。

String s = sc.next();
int n = s.length();
int firstsum[] = new int[n];//firstsum[i] stores the number of palindromes in the substring (0...i)
int[][] A = new int[n][n];//A[i][j]=1 denotes the substring (i...j) is a palindrome and =0 otherwise

for(int i=0;i<n;++i)
{
     A[i][i]=1;
}

for(int len=1;len<n;++len)
{
    for(int i=0;i<n-len;++i)
    {
        if( s.charAt(i)==s.charAt(i+len) && (i+1>=i+len-1 || A[i+1][i+len-1]==1) )
        {
            A[i][len]=1;
        }
        else{
            A[i][len]=0;
        }
    }
}


for(int i=0;i<n;++i)
{
    firstsum[i]=0;
    for(int j=0;j<=i;++j)
    {
        if(A[j][i]==1)
            firstsum[i]++;
    }
    if(i>0)
        firstsum[i]+=firstsum[i-1];
}
int cnt=0;
for(int i=1;i<n;++i)
{
    for(int j=i;j<n;++j)
        cnt+=A[i][j]*firstsum[i-1];
}
System.out.print(cnt);//answer