题解 | #Palindrome#

简要题意：给出一个字符串，求增加多少字符能使之回文
方法：串长减去最长回文子序列长度，即增加非最长回文串的内容
传统方法dp[i] [j]表示i到j最长回文串长度
若s[i]==s[j]，dp[i] [j]=dp[i+1] [j-1]+2
否则dp[i] [j] = max(dp[i+1] [j],dp[i] [j-1])
注意开一个5005*5005的int数组会爆空间
优化法一：改成short数组，short范围 -32768~32767，即-2^15 ~ 2^15-1

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
string s;
short dp[5005][5005];//i到j的最长回文子序列长度

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    cin >> s;
    s=" "+s;//使字符串有效下标从1到n
    for(int len=0;len<=n-1;len++){//区间长度
        for(int l=1;l<=n && l+len<=n ;l++){
            int r=l+len;
            if(r==l)    dp[l][r]=1;
            else if(s[l]==s[r])    dp[l][r]=dp[l+1][r-1]+2;
            else    dp[l][r]=max(dp[l+1][r],dp[l][r-1]);
        }
    }
    cout << n-dp[1][n] << "\n";

//    for(int i=0;i<n;i++){
//        for(int j=0;j<n;j++){
//            cout << dp[i][j] << " ";
//        }
//        cout << "\n";
//    }
    return 0;
}

优化法二：01滚动
上述求回文串的解法不好滚动，考虑将串反转后与原串求最长公共子序列。
若s[i]==t[j]，则dp[i] [j]=dp[i-1] [j-1]+1
否则dp[i] [j]=max(dp[i-1] [j],dp[i] [j-1])
01滚动时，只需把第一维对2取模，另外(i-1)%2=(i+1)%2

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
string s;
string t;
int dp[2][5005];//i到j的最长回文子序列长度

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    cin >> s;
    t=s;
    reverse(s.begin(),s.end());
    s=" "+s;t=" "+t;//使字符串下标从1开始，防越界

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(s[i]==t[j])
                dp[i%2][j]=dp[(i+1)%2][j-1]+1;
            else
                dp[i%2][j]=max(dp[(i+1)%2][j],dp[i%2][j-1]);
        }
    }

    cout << n-dp[n%2][n] << "\n";

//    for(int i=0;i<2;i++){
//        for(int j=0;j<n;j++){
//            cout << dp[i][j] << " ";
//        }
//        cout << "\n";
//    }
    return 0;
}