Problem3021--回文串

3021: 回文串

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

回文串是一个对称的字符串，即从左到右读和从右到左读是相同的字符串。现给定一个字符串，请计算出需要插入的最小字符数量使得字符串成为回文串。
例如，给定的字符串为"Ab3bd"可以转换为回文串"dAb3bAd"或"Adb3bdA",需要的插入的最小的字符数是2.

Input

第一行，是一个整数N，表示字符串的长度，3≤N≤5000
第二行，是一个长度为N的字符串，字符串中只包含大写字母、小写字母和数字

Output

输出使得输入的字符串变成回文串需要插入的字符的最少数量

Sample Input Copy 

5
Ab3bd

Sample Output Copy 

2

Source/Category

区间DP level6 
[Submit] [Status]