Số bước chèn tối thiểu để chuỗi thành palindrome trong C++

Cho chuỗi s, mỗi bước chèn bất kỳ ký tự nào tại vị trí bất kỳ. Tìm số ký tự chèn tối thiểu để s thành palindrome.

Ví dụ: "mad" → 2 (thêm "da" trước hoặc "am" sau).

Giải thuật

1. Số chèn tối thiểu = độ dài chuỗi - độ dài dãy con chung dài nhất (LCS) giữa s và reverse(s).
2. Tính LCS bằng DP 2D: dp[i][j] = LCS của s[1..i] và rev[1..j].
3. Trả về n - dp[n][n].

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int lcs(string s){
        string x = s;
        int n = s.size();
        reverse(x.begin(), x.end());
        s = " " + s;
        x = " " + x;
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if(s[i] == x[j]) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
            }
        }
        return dp[n][n];
    }
    int minInsertions(string s) {
        return s.size() - lcs(s);
    }
};
int main(){
    Solution ob;
    cout << (ob.minInsertions("mad"));
}

Đầu vào

"mad"

Đầu ra

2