Chương trình tìm dãy phép toán chuyển đổi xâu này sang xâu kia trong C++

Mô tả bài toán

Cho hai xâu S và T. Tìm dãy phép toán ngắn nhất (chèn/xóa ký tự) biến S thành T. Phép toán: giữ ký tự (xuất ký tự), xóa (đánh dấu '-'), chèn (đánh dấu '+').

Ví dụ: S="xxxy", T="xxyy" → ["x","x","-x","y","+y"].

Giải thuật (DP + truy vết)

1. dp[i][j] = số phép tối thiểu từ S[i:] và T[j:].
2. Cơ sở: i==|S| && j==|T| → 0; i==|S| → 1+dp[i][j+1]; j==|T| → 1+dp[i+1][j].
3. Chuyển trạng thái: nếu S[i]==T[j] thì dontDo = dp[i+1][j+1]; del = 1+dp[i+1][j]; ins = 1+dp[i][j+1]; dp[i][j] = min(dontDo, del, ins).
4. Truy vết từ (0,0) theo dp để xây dựng dãy phép toán.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

int dp[505][505];

class Solution {
public:
    int help(int i, int j, string& S, string& T) {
        if (i == S.size() && j == T.size()) return dp[i][j] = 0;
        if (i == S.size()) return dp[i][j] = 1 + help(i, j+1, S, T);
        if (j == T.size()) return dp[i][j] = 1 + help(i+1, j, S, T);
        if (dp[i][j] != -1) return dp[i][j];
        int dontDo = 1e5, del = 0, ins = 0;
        if (S[i] == T[j]) dontDo = help(i+1, j+1, S, T);
        del = 1 + help(i+1, j, S, T);
        ins = 1 + help(i, j+1, S, T);
        return dp[i][j] = min({dontDo, del, ins});
    }
    void getPath(int i, int j, string& S, string& T, int cur, vector<string>& ret) {
        if (cur == 0 && i == S.size() && j == T.size()) return;
        if (i < S.size() && j < T.size() && S[i] == T[j] && dp[i+1][j+1] == cur) {
            ret.push_back(string(1, S[i]));
            getPath(i+1, j+1, S, T, cur, ret);
        } else if (dp[i+1][j] + 1 == cur) {
            ret.push_back("-" + string(1, S[i]));
            getPath(i+1, j, S, T, cur-1, ret);
        } else {
            ret.push_back("+" + string(1, T[j]));
            getPath(i, j+1, S, T, cur-1, ret);
        }
    }
    vector<string> solve(string S, string T) {
        memset(dp, -1, sizeof dp);
        vector<string> ret;
        int x = help(0, 0, S, T);
        getPath(0, 0, S, T, x, ret);
        return ret;
    }
};

int main() {
    string S = "xxxy", T = "xxyy";
    Solution ob;
    for (auto& op : ob.solve(S, T)) cout << op << ' ';
    return 0;
}

Đầu vào

"xxxy", "xxyy"

Đầu ra

x x -x y +y