题解 P1435 【回文字串】

Jelly_Goat · 2019-04-28 15:44:22 · 题解

刚学区间dp，我来写一篇题解
这个题就是经典的序列（子串）问题的变种。

思路：

我们发现，我们只需要求出最长回文子序列来，
然后用原字符串长度减去最长回文子序列的长度即可。

证明：

对于回文的，已经算在最长回文子序列的长度中，其他的非回文的，就可以填上一个字母。
于是乎，需要给非回文填上的字母个数即原先的长度减去最长回文子序列的长度。

本题关键：求最长回文子序列的长度

定义：dp[10001][10001]，二维dp，第一维枚举区间长度，第二维枚举起点。
预处理：首先本身一个字母是一个回文字符串。即dp[i][i]=1。
然后我们结合代码理解一下~

for (int step = 1; step < n; step++)
{
    //区间起点
    for (int i = 1; i + step <= n; i++)
    {
        //区间终点
        int j = i + step;
        //首先可以是子串[i+1->j]的最...长度或者子串[i->j-1]的...长度
        dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        //然后如果两个字母是相同的且是区间端点，就还有一个转移方式
        if (str[i] == str[j])
        {//使用子串[i+1->j-1]的...长度和原先的长度进行比较，选择一个更大的
            dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
        }
    }
}

是够经典的...
于是乎我们就知道最长的...串的长度就是dp[1][n]。
所以最后答案就是n-dp[1][n]。
然后放上我的代码qwq

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;
const int mod = 1e9 + 7;
char str[10001];
int n;
int dp[10001][10001];

int main()
{
    scanf("%s", str+1);
    n=strlen(str+1);
    for (int i = 1; i <= n; i++)
    {
        dp[i][i] = 1;
    }
    for (int step = 1; step < n; step++)
    {
        for (int i = 1; i + step <= n; i++)
        {
            int j = i + step;
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            if (str[i] == str[j])
            {
                dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
            }
        }
    }
    printf("%d\n", n-dp[1][n]);
    return 0;
}

需要注意的是，我们在循环中直接使用了str[i]和str[j]，而这两个下标其中j可能是n。
所以需要从str+1开始读入。