POJ1159-Palindrome 最长公共子序列+滚动数组

这个题比较容易想到要添加最少的字母其实就是保留原串和原串的逆序串的最长公共子序列，其它的字母补全。但是这道题的内存不太够，因为dp[i][j]第一维只与前面一个字母有关，所以可以优化。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 1e5 + 10;

void acc_ios()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
}

char s[maxn], t[maxn];
int dp[2][maxn];
int main()
{
    acc_ios();
    int n;
    cin>>n;
    cin>>(s + 1);
    for(int i = 1; i <= n; i++)
    {
        t[i] = s[n - i + 1];
    }
    int now = 0;
    for(int i = 1; i <= n; i++)
    {
        now = !now;
        for(int j = 1; j <= n; j++)
        {
            if(s[i] == t[j]) dp[now][j] = dp[!now][j - 1] + 1;
            else
            {
                dp[now][j] = max(dp[now][j - 1], dp[!now][j]);
            }
            
        }
    }
    cout<<n-dp[now][n]<<endl;
    return 0;
}

本文地址：https://blog.csdn.net/weixin_43891021/article/details/109630290