UVa 10453 Make Palindrome（简单DP）

题意：

给定一个字符串，问最少插入多少个字符使其变成回文字符串，并输出。

思路：

题目已经是司空见惯了，关于回文串的输出无非就是递归。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1010;
char str[MAXN];
int dp[MAXN][MAXN];

void output(int i, int j)
{
    if (i == j)
        printf("%c", str[i]);
    else if (str[i] == str[j])
    {
        printf("%c", str[i]);
        if (i + 1 <= j - 1)
            output(i + 1, j - 1);
        printf("%c", str[j]);
    }
    else
    {
        if (dp[i+1][j] < dp[i][j-1])
        {
            printf("%c", str[i]);
            output(i + 1, j);
            printf("%c", str[i]);
        }
        else
        {
            printf("%c", str[j]);
            output(i, j - 1);
            printf("%c", str[j]);
        }
    }
}

int main()
{
    while (scanf("%s", str) != EOF)
    {
        int n = strlen(str);
        for (int i = 0; i < n; ++i)
        {
            dp[i][i] = 0;
            if (str[i] == str[i+1])
                dp[i][i+1] = 0;
            else
                dp[i][i+1] = 1;
        }

        for (int p = 2; p < n; ++p)
        {
            for (int i = 0, j = p; j < n; ++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;
            }
        }
        printf("%d ", dp[0][n-1]);
        output(0, n - 1);
        printf("\n");
    }
    return 0;
}