425.c

/*
	Solution for the problem 425 of aceptaelreto.com

	- Aibofobia - 

    Copyright (C) 2018 hnko
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
#include <stdio.h>
#include <string.h>

int max(int a, int b){return (a>b)?a:b;}
int cache[101][101];
char palabra[101];

int palindromo(int i, int j){
	if(i > j ) return 0;
	if(i == j) return 1;
	if(cache[i][j] != -1) return cache[i][j];

	int resultado;
	if(palabra[i] == palabra[j]){
		resultado = 2 + palindromo(i+1, j-1);
	}else{
		resultado = max(palindromo(i+1, j), palindromo(i, j-1));
	}
	cache[i][j] = resultado;
	return resultado;
}

int main(int argc, char const *argv[])
{
	while(scanf("%s", palabra) != EOF){
		int len = strlen(palabra), i, j;
		for(i=0;i<len; i++){
			for(j=0; j<len; j++){
				cache[i][j] = -1;
			}
		}
		printf("%d\n", len - palindromo(0, strlen(palabra)-1));
	}
	return 0;
}