题目是求最长回文子序列的长度，不过其区间的选取是有点讲究的。
首先把源串复制一遍，放在后面以解决循环的问题。随后用动态规划求其最长回文子序列。这里不能直接把最大值求出来就完事，题目要求了不能走重复的路，换言之，其区间窗口最长只能为n。
一开始我以为只要把最大值求出来和n取min就好，之后发现这个最大值不一定能满足不走重复路的约定，所以我们在查找区间的时候，要控制区间长度。取dp[i][i+n-1]这还没完,比如1213这种数据，可以从3开始最后跳到2，回文串为1213121，如果用n去控制则会输出3下，显然不对。究其原因，是回文串的中心位可以为一个单独的数，所以其长度有奇偶之分，所以窗口大小也要能同时处理奇偶，这里就可以用dp[i][i+n-2]+1了将dp窗口-1，那减去的一位作为起跳点。
直接上代码吧。
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; int s1[2005]; int dp[2005][2005]; int main() { int n; while(cin>>n) { if(n==0) break; for(int i=0;i<n;i++) { cin>>s1[i],s1[i+n]=s1[i]; } for(int i=0;i<n*2;i++) for(int j=0;j<n*2;j++) dp[i][j]=(i==j); int mx=1; for(int i=n*2-1;i>=0;i--) { for(int j=i+1;j<n*2;j++) { if(i<j) { if(s1[i]==s1[j]) dp[i][j]=dp[i+1][j-1]+2; else dp[i][j]=max(dp[i+1][j],dp[i][j-1]); } } } int ans=0; for(int i=0;i<n;i++) { ans=max(ans,dp[i][i+n-1]); ans=max(ans,dp[i][i+n-2]+1); } cout<<ans<<endl; } return 0; }
原文：http://www.cnblogs.com/LukeStepByStep/p/6696343.html