Question

一个字符串s，最少需要删除多少个字符才能使字符串S

Answer 1

输入一个字符串，求最少需要删除多少个字符才能使字符串S变为回文串。 例如，输入“cabebaf”，则删除‘c' ,'f'' 之后字符串变为“abeba”，从而，至少删除2个字符串之后原字符串变为回文字符串。（PS：第一次写文章，有描述不清的地方还请指教）

题目分析：
变量申明：设输入字符串为S，其长度为len，字符串转换为字符数组表式为Ch，S（i，j）表式Ch下标从i到j的字串（0<=i<j<len），f(i, j)表式字串S(i，j）变为回文串至少需要删除的字符数。result为某个字符串所需的最少删除字符的数量。
原理说明：1：若字符串长度len为1，不需要删除任意字符，return 0；若字符串长度len为2，return 0（相同）或者return 1（不同）；
2：若len>1,若需要求子串S(i,j+1)的最少删除的字符数f(i,j+1)，可以分两种情况：
1）：若Ch[j+i] == Ch[i] (即字串前后两个字符相同) ，则f(i,j+1) = f(i+1, j) （与除去S(i,j+1)字串前后两个字符的所得串S(i+1,j)相同）；
2）：若Ch[j+i] != Ch[i] (即字串前后两个字符不同)，则f(i,j+1) = min（ f(i, j)， f(i+1, j+1)）+1；
3：由2分析可知，要求串长为 j-i+2 的子串S(i,j+1)的f(i,j+1)，只需知道串长为 j-i+1 的子串 f(i, j)和f(i+1, j+1)的删除数f，或者串长为 j-i 的子串f(i+1, j) 的f即可。由1分析可知，我们已经知道了串长为1和2的所有子串的f。 因而，我们只需要依次求出串长从 3 到 len 的所有f即可。

实现说明：1：申请一个int[len][len] 的二维数组res；res(i,j)代表长度为 i 的子串的S(j-i+1, j)变为回文串至少需要删除的字符数，由此可知，res第i行的前 i-1 个记录是无效记录。（前i-1个字符凑不齐长度为i的串）。
2：根据原理说明中的2、3步骤依次计算res，最后返回res的最后一个记录，即为所求。
3：由于计算串长为k的res时，只需要知道串长为k-1和k-2的res即可，因而在实现的过程中，申请res数组时，只申请int[3][len],计算时交替覆盖k-3所在的行，可大幅减少所用内存。
* 最少需要删除多少个字符才能使字符串S变为回文串
* 原理：令f(i,j)表式S串中从i-j的字串，则
* 1：如果S(i)==S(j+1)----> f(i,j+1)=f(i+1,j)
* 2:如果S(i)！=S(j+1)----> f(i,j+1)=Math.min（f(i,j),f(i+1,j+1)）+1
* 令S串长为len，构造len*len矩阵，
* @param s 输入字符串
* @return 最少删除数
*/
public static int reverse(String s){
if(s==null || s.length()<2)
return 0;
int len = s.length();
char[] ch = s.toCharArray();
int[][] res = new int[3][len];
for(int i=2;i<len;++i){
int t = i%3;
for(int j=0;j<len-i;++j){
if(ch[j]==ch[j+i])
res[t][j+i]=res[f(t-2)][j+i-1];
else
res[t][j+i]=Math.min(res[f(t-1)][j+i-1], res[f(t-1)][j+i])+1;
}
}
return res[(len-1)%3][len-1];
}
public static int f(int n){
return n<0?n+3:n;
}