回文字符串(求出至少需要补充多少个元素使得成回文)

描述

所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如"aba"。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。

输入

第一行给出整数N（0<N<100）
接下来的N行，每行一个字符串，每个字符串长度不超过1000.

输出

每行输出所需添加的最少字符数

样例输入

1
Ab3bd

样例输出

解题思路：

利用动态规划的思想。参考括号匹配问题(括号匹配)。几乎一模一样。

 1  public static int plalindrome(int i, int j, string s)
 2         {
 3             if (i == j)
 4                 return M[i, j] = 0;
 5             if (i > j)
 6                 return 0;
 7             if (M[i, j] != -1)
 8                 return M[i, j];
 9             if (i == j - 1 && s[i] != s[j])
10                 return M[i, j] = 1;
11             if (s[i] == s[j])
12                 return M[i, j] = plalindrome(i + 1, j - 1, s);
13             return M[i, j] = Math.Min(plalindrome(i, j - 1, s), plalindrome(i + 1, j, s)) + 1;
14         }

View Code