动态规划求最长回文子序列模板

子序列是不连续的，子串是连续的。

 1 #include<stdio.h> 
 2 #include<string.h>
 3 #include<iostream>
 4 using namespace std;
 5 const int N=1111;
 6 int f[2][N],a[N];
 7 int main()
 8 {
 9     int t,n,i,j;
10     scanf("%d",&t);
11     while(t--)
12     {
13         scanf("%d",&n);
14         for(i=1;i<=n;i++)
15             scanf("%d",&a[i]);
16         memset(f,0,sizeof(f));
17         int now=0;
18         for(i=n;i;--i)
19         {
20             f[now][i]=1;
21             for(j=i+1;j<=n;j++)
22             {
23                 if(a[i]==a[j])
24                     f[now][j]=f[1-now][j-1]+2;
25                 else
26                     f[now][j]=max(f[1-now][j],f[now][j-1]);
27             }
28             now=1-now;
29         }
30         if(n%2==0)
31             printf("%d
",f[1][n]);
32         else
33             printf("%d
",f[0][n]);
34     }
35     return 0;
36 }

滚动数组，空间复杂度为O(N)。时间复杂度O(N^2)。上面的代码是2016中南大学校赛的J题。