洛谷题单指南-动态规划2-P1435 [IOI2000] 回文字串

原题链接：https://www.luogu.com.cn/problem/P1435

解题思路：

方法1：

回文字串的特点是，正着读、反着读是一样的

换一个思路，对于一个字符串s，正序、逆序公共的部分就是已经是回文的部分，剩余的部分就是要插入的字符

所以，问题转换为，计算一个字符串正序、逆序的最长公共子串，然后剩下的长度即要插入的最少字符数。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
string s;
int dp[N][N]; // dp[i][j]表示正序1~i，逆序len~j的最长公共子序列

int main()
{
    cin >> s;
    int l = s.length();
    s = " " + s;
    for(int i = 1; i <= l; i++)
    {
        for(int j = l; j >= 1; j--)
        {
            if(s[i] == s[j]) dp[i][j] = dp[i-1][j+1] + 1;
            else dp[i][j] = max(dp[i][j+1], dp[i-1][j]);
        }
    }

    cout << l - dp[l][1];

    return 0;
}

方法2：

设dp[i][j]表示把i~j变成回文字串需要插入的最少字符数

设字符串为s

如果s[i] == s[j]，dp[i][j] = dp[i+1][j-1]，和i+1 ~ j-1的结果一致

否则，可以在i前面插入s[j],也可以在j后面插入s[i]，取较小值，dp[i][j] = min(dp[i][j-1] + 1, dp[i+1][j] + 1);

由于最终结果是dp[1][s.length()]，i要从大到小遍历，j要从小到大遍历，且保证i <= j

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
string s;
int dp[N][N]; // dp[i][j]表示把i~j变成回文字串需要插入的最少字符数

int main()
{
    cin >> s;
    int l = s.length();
    s = " " + s;
    for(int i = l; i >= 1; i--) 
    {
        for(int j = i; j <= l; j++)
        {
            if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1];
            else
            {
                //可以在i前面插入s[j],也可以在j后面插入s[i]
                dp[i][j] = min(dp[i][j-1] + 1, dp[i+1][j] + 1);
            }
        }
    }

    cout << dp[1][l];

    return 0;
}