给一字符串，问最少加几个字符能够让它成为回文串。

比方 Ab3bd 最少须要两个字符能够成为回文串 dAb3bAd

思路：

动态规划 DP[i][j] 意味着从 i 到 j 这段字符变为回文串最少要几个字符，枚举子串长。

if str[i] == str[j]:

DP[i][j] = DP[i + 1][j - 1]

else:

DP[i][j] = min( DP[i + 1][j], DP[i][j - 1] ) + 1

注意：

长度较大为 5000，二维数组 5000 * 5000 须要将类型改为 short，

不需考虑 j - i < 2 的特殊情况，

由于矩阵的左下三角形会将DP[i + 1][j - 1]自己主动填零，

可是用滚动数组的时候须要考虑 j - i < 2。用滚动数组的时候，空间会变为 3 * 5000,

可这时候 DP 的含义略微变下。

DP[i][j] 意味着从第 j 个字符右移 i 个长度的字符串变为回文串所须要的最少字符数目。

3.也能够用 LCS 的方法，字符串长 - LCS( 串。逆串 ) 

#include <iostream>

#include <cstring>

using namespace std;

int nLen;

char str[5005];

short DP[5005][5005];

int main(){

    memset( DP, 0, sizeof( DP ) );

    cin >> nLen;

    cin >> str;

    for( int len = 1; len < nLen; ++len ){

        for( int start = 0; start + len < nLen; ++start ){

            int end = start + len;

            if( str[start] == str[end] )

                DP[start][end] = DP[start + 1][end - 1];

            else

                DP[start][end] = min( DP[start + 1][end], DP[start][end - 1] ) + 1;

        }

    }

    cout << DP[0][nLen - 1];

    return 0;

}

滚动数组 715K：

#include <iostream>

#include <cstring>

using namespace std;

int nLen;

char str[5005];

short DP[3][5005];

int main(){

    memset( DP, 0, sizeof( DP ) );

    cin >> nLen;

    cin >> str;

    for( int len = 1; len < nLen; ++len ){

        for( int start = 0; start + len < nLen; ++start ){

            int end = start + len;

            if( str[start] == str[end] && ( end - start >= 2 ) )

                DP[len % 3][start] = DP[( len - 2 ) % 3][start + 1];

            else if( str[start] != str[end] )

                DP[len % 3][start] = min( DP[( len - 1 ) % 3][start + 1],

                                         DP[( len - 1 ) % 3][start] ) + 1;

        }

    }

    cout << DP[(nLen - 1) % 3][0];

    return 0;

}