http://acm.pku.edu.cn/JudgeOnline/problem?id=1159

   Задача: Палиндром
   Палиндром - это симметричная строка, то есть она одниково читается как слева направо, так и справа налево. Вы должны написать программу, которая по заданной строке определяет минимальное количество символов, которе необходимо вставить в строку для образования палиндрома.
   Например, вставкой двух символов строка "Ab3bd"  может быть преобразована в палиндром ("dAb3bDd"или "Adb3bdA"), а вставкой меньше двух символов палиндром в этом примере получить нельзя.

   Входные данные:
   Первая строка содержит одно целое число - длину N входной строки, 3 <= N <= 5000. Вторая - строку длины N, которая состоит из прописных (заглавных) букв от "A" до "Z", строчных букв от "a" до "z" и цифр от "0" до "9". Прописные и строчные буквы считаются различными.

   Входные данные:
   В единственной строке вывести одно целое число, которое является искомым минимальным числом символов.

   Пример входных данных:
Ab3bd

   Пример выходных данных:
2

Анализ условия и разбор решения:

Код:
#include <stdio.h>
 
#define MAX(a,b) ((a) > (b) ? (a) : (b))
 
short T[5005][5005];
 
int main()
{
    int N, i,j;
    char s[5005];
 
    scanf("%d %s", &N, s+1);
 
    for(i=1;i<=N;i++) {
        for(j=1;j<=N;j++) {
            if(s[j]==s[N-i+1]) T[i][j]=T[i-1][j-1]+1;
            else T[i][j] = MAX(T[i-1][j], T[i][j-1]);
        }
    }
 
    printf("%d\n", N-T[N][N]);
    return 0;
}