11503번: Tree Edit

https://www.acmicpc.net/problem/11503

T1, T2의 각 노드에 서로 다른 번호가 부여되어 있다고 하자.
i번 노드의 자식들을 ci_1, ci_2, ...라고 하자.
ed[i][j]: i번 노드가 루트인 T1의 서브트리를 j번 노드가 루트인 T2의 서브트리로 바꾸는데 필요한 최소 편집 연산 수
ed[i][j]는 ed[ci_1..n][cj_1..m]들을 가지고 DP로 구할 수 있다.

dp[u][v]: ci_1..u 를 cj_1..v로 바꾸는데 필요한 최소 편집 연산 수
dp[u][v] = min(
dp[u-1][v] + (ci_u가 루트인 서브트리의 사이즈),
dp[u][v-1] + (cj_v가 루트인 서브트리의 사이즈),
dp[u-1][v-1] + ed[ci_u][cj_v])
그러면 ed[i][j]는 dp[n][m]이 된다.

시간복잡도는 $O(n^2)$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int tc, ed[2000][2000], sz[2000], pos, id;
char la[2000], s[3001];
vector<int> adj[2000];
int f(int l, int r) {
    if (~ed[l][r]) return ed[l][r];
    int n = adj[l].size(), m = adj[r].size();
    vector<vector<int> > dp(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + sz[adj[l][i - 1]];
    for (int i = 1; i <= m; i++) dp[0][i] = dp[0][i - 1] + sz[adj[r][i - 1]];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        dp[i][j] = min({ dp[i][j - 1] + sz[adj[r][j - 1]],
            dp[i - 1][j] + sz[adj[l][i - 1]],
            dp[i - 1][j - 1] + f(adj[l][i - 1], adj[r][j - 1]) });
    return ed[l][r] = dp[n][m] + (la[l] != la[r]);
}
void gen() {
    int h = id++, st = pos;
    adj[h].clear();
    la[h] = s[++pos];
    while (s[++pos] != ')') adj[h].push_back(id), gen();
    sz[h] = (pos - st) / 3 + 1;
}
void solve() {
    fill(&ed[0][0], &ed[1999][2000], -1);
    scanf("%s", s); id = pos = 0; gen();
    int t = id;
    scanf("%s", s); pos = 0; gen();
    printf("%d\n", f(0, t));
}
int main() {
    for (scanf("%d", &tc); tc--;) solve();
    return 0;
}