1092 回文字符串

解题思想

/*
 应为本题只是简单的求构成回文串的所需要添加的最小数目，
 所以可以直接先将原串倒置，然后求俩串的最长公共字序列len，
 最终结果就是串的长度减去len，
 为什么这样做是对的呢？
 因为倒置的串首先长度是一样的，然后求倒过来跟原串一个个按顺序
 比是不是一样的，一样的说明可以构成回文，可能只是顺序不对应罢了

*/

代码

/*
#include<iostream>
#include<cstring>
using namespace std;
#define MAXN 1001
char a[MAXN], b[MAXN];
int dp[MAXN][MAXN];
int main()
{
    cin >> a;
    int lena =(int) strlen(a);
    //原串倒置
    for(int i=0; i<lena; ++i)
        b[i] = a[lena-i-1];
        //求最长公共子序列
        //dp[i][j]表示串a[0..i-1] 与串b[0..j-1]的
        //最长公共字序列的长度
    for(int i=1; i<lena+1; ++i)
        for(int j=1; j<lena+1; ++j)
    {
        if(a[i-1] == b[j-1])
            dp[i][j] = dp[i-1][j-1] + 1;
        else
        {
            dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
        }

    }
    cout << lena - dp[lena][lena] <<endl;
}
*/