https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1680

10739 - String to Palindrome.cpp

    #include <bits/stdc++.h>

    #define ll long long
    #define sz(v) ((int) ((v).size()))
    #define clr(v, d) memset(v, d, sizeof(v))
    #define lp(i, n) for(int i = 0; i < (int)(n); ++i)
    #define rep(i, v) for(int i = 0; i < sz(v); ++i)

    using namespace std;

    const int OO = 10000;
    const int MAX = 1001;
    int n;
    string s;
    int cache[MAX][MAX];

    int minPale(int st, int en) {
        if(st>=en)
            return 0;

        int &ret = cache[st][en];
        if(ret != -1)
            return ret;
        ret = OO;
        if(s[st] == s[en])
            ret = minPale(st+1, en-1);
        else {
            ret = min(minPale(st+1, en)+1, min(minPale(st, en-1)+1, minPale(st+1, en-1)+1));
        }
        return ret;
    }

    int main() {
        cin >>n;
        lp(i, n) {
            clr(cache, -1);
            cin>>s;
            cout<<"Case "<<i+1<<": "<<minPale(0, s.length()-1) << endl;
        }
        return 0;
    }