【腾讯笔试】构造回文（最大公共子序列）

1、题目描述

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。

2、状态表示：

• 将输入的字符翻转，判断最长的公共子序列，用字符串的长度，减去公共字符串的长度就是答案。
• 即求最长公共字符串，f[i][j] 表示s1的前i个和s2的前j个最长公共字符串。

3、状态转移：

f[i][j] = f[i - 1][j - 1] + 1, 如果第i个和第i个相同。
f[i][j] = max(f[i - 1][j], f[i] [j - 1]),如果两个不相同。

4、C++代码：

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
const int N = 1010;
int f[N][N];//N为const，默认初始化为0.
int maxlen(string s1, string s2) {//求最长公共子序列。
    int l1 = s1.size();
    int l2 = s2.size();
        此句话删掉。f[][]默认全部初始化为0；
    for (int i = 1; i <= l1; i ++) //避免边界条件，从1开始。所以是<=
        for (int j = 1; j <= l2; j ++) {
            if (s1[i - 1] == s2[j - 1]) 
                f[i][j] = f[i - 1][j - 1] + 1;
            else
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    return f[l1][l2];
}
int main() {
    string s;
    while(cin >> s) {
        int l = s.size();
        if (l == 1) {
            cout << 1 << endl;
        }
        string s2 = s;
        reverse(s2.begin(), s2.end());//字符串翻转。
        int length = maxlen(s, s2);//最长公共子序列。
        cout << l - length << endl;
    }
    return 0;
}