最长回文子序列

#include <bits/stdc++.h>
using namespace std;
int dp[10000][10000];
int lcs(string str,int n){
    int  tmp;
    memset(dp,0,sizeof(dp));
    for(int i=0; i<n; i++) dp[i][i] = 1;
    for(int i=1; i<n; i++){
        tmp = 0;
        for(int j=0; j+i<n; j++){
            if(str[j] == str[j+i]){
                tmp = dp[j+1][j+i-1] + 2;
            }else{
                tmp = max(dp[j+1][j+i],dp[j][j+i-1]);
            }
            dp[j][j+i] = tmp;
        }
    }
    return dp[0][n-1];
}
int main()
{
    string s;
    int n;cin>>n;
    while(n--)
    {
        cin>>s;
        int x=lcs(s,s.length()),len=s.length();
        printf("%d\n",len-x);
    }
    return 0;
}