AIBOHP-Aibohphobia

Aibohphobia

Given below code is for AIBHOP spoj or aibohphobia spoj.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 27 September 2015 (Sunday) 22:47
===================================================*/
#include <bits/stdc++.h>
using namespace std;
int dp[6101][6101];
char s[6109];
int rec( int i , int j){
    if(i > j)
        return INT_MAX;
    if(i == j)
        return 0;
    if(i == j -1 )
        return s[i] == s[j] ? 0 : 1;
    if(dp[i][j] != -1)
        return dp[i][j];
    if(s[i] == s[j]){
        return dp[i][j] = rec(i+1 , j-1);
    }
    else {
        return dp[i][j] = min(rec(i+1 , j) , rec(i , j-1)) + 1;
    }
}
int main(){
 
    int t;
    scanf("%d", &t);
    while(t--){
        memset(dp , -1 , sizeof dp);
        scanf("%s",s);
        int len = strlen(s);
        printf("%d\n",rec(0 , len-1));
    }
    return 0;
}