回文词的研究

题目

回文词
【问题描述】
回文词是一种对称的字符串，也即：一个回文词从左到右读和从右到左读得到的结果是一样的。给定任意一个字符串，通过插入若干字符，都可以变为一个回文词。我们所感兴趣的是，如何在插入最少字符的情况下，将给定字符串变为回文词。请编程实现。
例如：字符串“Ab3bd”，只需插入两个字符后就可变为回文词（“dAb3bAd”和“Adb3bdA”）
【输入数据】
输入数据第一行是一个整数N（3≤N≤5000），表示字符串的长度；第二行是一个长度为N的字符串，仅由大写字母‘A’到‘Z’、小写字母‘a’到‘z’组成，严格区分大小写。
【输出数据】
输出需要最小插入的字符数，以及形成的回文字符串。
思路
回文词就是正序和反序读是一样的字符串。
在这道题目里比往常的题目多了一个要求，就是要输出添加字符后的回文字符串。看起来很简单的要求对吧，那我们就先不管这个要求，把常规的要求写出来。

动态规划

首先，我们来将待求解问题分解成若干个子问题，这道题里应该怎么分解呢。
我们把字符串用一个字符数组表示，开始的位置是beg，结束的位置是end，那么[beg，end]这个字符串要添加的字符就是
1.字符串两端字符相同，那么需要添加的字符个数就是[beg+1，end-1]这个字符串变为回文字符串所需要添加的字符数。列成式子就是fun(beg,end)=fun(beg+1,end-1)。
2.字符串两端字符不相同相同，那么需要添加的字符个数就是[beg+1，end]和[beg，end-1]这两个字符串变为回文字符串所需要添加的字符数中较小的那一个加1。列成式子就是fun(beg,end)=min(fun(beg,end-1),fun(beg+1,end))+1。
子问题也可以不停的分解，知道当字符串长度小于等于1，也就是beg>=end的时候，需要添加的字符数就是0。
所以我们已经可以写出最核心的代码了。

int fun(int beg, int end) {
    if (beg >= end)
        return 0;
    if (str[beg] != str[end])//str就是字符数组
        return min(fun(beg, end - 1), fun(beg + 1, end)) + 1;
    if (str[beg] == str[end]) {
        return fun(beg + 1, end - 1);
    }
}

但是这只是分治法呀，动态规划与分治法的区别就是动态规划的子问题会相同，我们就可以用一个数组保存下已经计算过的子问题的答案，第二次需要时就不用再计算一次了。改进后的代码如下

int fun(int beg, int end) {
    if (beg >= end)
        return 0;
    if (str[beg] != str[end]) {                                         //str就是字符数组
        useful[beg][end - 1] || useful[beg][end - 1] = fun(beg, end - 1);  //好高级的写法呀！！！
        useful[beg + 1][end] || useful[beg + 1][end] = fun(beg + 1, end);  //useful[beg][end]就是字符串[beg,end]
        return min(useful[beg][end - 1], useful[beg + 1][end]) + 1;     //所需要添加的字符数，如果已经计算过
    }                                                                     //就不用在计算一次了，直接读取。如果
    if (str[beg] == str[end]) {                                         //没有计算过，就计算并保存下来。
        useful[beg + 1][end - 1] || useful[beg + 1][end - 1] = fun(beg + 1, end - 1);
        return useful[beg + 1][end - 1];
    }
}

这就是动态规划了。先写到这里，明天继续。
但是我们需要得出形成的回文词呀，这样子明显是不行的，但是我们可以用一个字符串来保存形成的回文词呀，我们先试一下吧。