UVa 10739 - String to Palindrome

10739.cpp

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

#define F first
#define S second
#define PB push_back
#define endl '\n'

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

string S;
int dp[1007][1007];

int f(int i, int j) {
    if(i >= j) return 0;
    if(~dp[i][j]) return dp[i][j];

    if(S[i] == S[j])
        return dp[i][j] = f(i + 1, j - 1);

    int &answ = dp[i][j];
    answ = f( i + 1, j ) + 1;
    answ = min(answ, f( i, j - 1 ) + 1);
    answ = min(answ, f(i + 1, j - 1) + 1);

    return answ;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for(int i=1; i<=t; i++) {
        memset(dp, -1, sizeof dp);

        cin >> S;
        printf("Case %d: %d\n", i, f( 0 , S.size() - 1 ));
    }

    return 0;
}