目录

题目

P1435 [IOI 2000] 回文字串

算法标签: 动态规划, 线性 d p dp dp

思路

因为是线性 d p dp dp, 考虑能否用一维表示当前状态, 发现想要判断当前字符串是否是回文串是比较困难的, 因此可以使用二维表示当前状态 f [ i ] [ j ] f[i][j] f[i][j]表示 i i i到 j j j构成回文串所需要的最小添加字符数量, 状态转移将集合分为两类, 如果当前位置 s [ i ] = s [ j ] s[i] = s[j] s[i]=s[j], 那么就可以由 f [ i + 1 ] [ j − 1 ] f[i + 1][j - 1] f[i+1][j−1]转移过来, 如果 s [ i ] ≠ s [ j ] s[i] \ne s[j] s[i]=s[j], 那么只能由 f [ i + 1 ] [ j ] f[i + 1][j] f[i+1][j]或者 f [ i ] [ j − 1 ] f[i][j - 1] f[i][j−1]进行转移, 当然因为当前字符不相等因此还需要 + 1 + 1 +1, 算法时间复杂度 O ( n 2 ) O(n ^ 2) O(n2), 数据范围是 1000 1000 1000可以通过

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

string s;
int n, f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> s;
    n = s.size();
    s = ' ' + s;

    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++i) f[i][i] = 0;

    for (int len = 2; len <= n; ++len) {
   
        for (int i = 1; i + len - 1 <= n; ++i) {
   
            int j = i + len - 1;
            if (s[i] == s[j]) {
   
                len == 2 ? f[i][j] = 0 : f[i][j] = f[i + 1][j - 1];
            }
            else f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
        }
    }

    cout << f[1][n] << "\n";
    return 0;
}