[hihoCoder - 1323] 回文字符串

发表于 | 更新于 | 分类于 ， ，
本文字数： 16k

链接

\(\text{hihoCoder - 1323}\)

题意

  给定一个字符串\(\text S\) ，最少需要几次增删改操作可以把\(\text S\)变成一个回文字符串？一次操作可以在任意位置插入一个字符，或者删除任意一个字符，或者把任意一个字符修改成任意其他字符。输出最少的操作次数。

  数据范围：字符串\(\text S\)。\(\text S\)的长度不超过\(100\), 只包含\(\text{A-Z}\)。

分析

  这是一道区间\(dp\)的题目；也是经典的最少操作次数变成回文串的问题；对于

  \(dp[i][j]\)表示\([i,j]\)区间的子串变成回文串最少操作次数，对于一个串\(bab\)，我们已经知道区间长度为\(2\)的所有状态，对于区间长度为\(3\)的阶段，此时\(s[i]==s[j]\)，那么显然有\(dp[i][j]=dp[i+1][j-1]\)，对于一个串\(bba\)，此时\(s[i]!=s[j]\)，此时来说，我们只需要修改\(s[i]\)为\(s[j]\)或者修改\(s[j]\)为\(s[i]\)即可，所以我们有\(dp[i][j]=\min\{dp[i+1][j]+1,dp[i][j-1]+1\}\)。

  初始状态\(dp[i][i]=0\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991

typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
    //char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar(); int x = 0, f = 1;
        while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
        while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}

using namespace fastIO;
using namespace std;

namespace segment_Tree {
    struct Tree {
        int l, r, max;
    } tree[4 * MAXN];

    inline void push_up(int x) {
        tree[x].max = max(tree[x << 1].max, tree[x << 1 | 1].max);
    }

    inline void build(int x, int l, int r) {
        tree[x].l = l, tree[x].r = r;
        if (l == r) {
            tree[x].max = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        push_up(x);
    }

    inline void update(int x, int pos, int val) {
        int l = tree[x].l, r = tree[x].r;
        if (l == r) {
            tree[x].max = max(tree[x].max, val);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)update(x << 1, pos, val);
        else update(x << 1 | 1, pos, val);
        push_up(x);
    }

    inline int query(int x, int l, int r) {
        int le = tree[x].l, ri = tree[x].r;
        if (l <= le && ri <= r) {
            return tree[x].max;
        }
        int mid = (le + ri) >> 1;
        int maxm = 0;
        if (l <= mid) maxm = max(maxm, query(x << 1, l, r));
        if (r > mid) maxm = max(maxm, query(x << 1 | 1, l, r));
        return maxm;
    }
}

int t, n, m, a[509], dp[10009][509];
string s;
int main() {
    cin >> s;
    int n = s.size();
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1);
            if (s[i - 1] == s[j - 1])dp[i][j] = dp[i + 1][j - 1];
            else {
                dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + 1);
            }
        }
    cout << dp[1][n] << endl;
}