SW练习_P1435 回文字串_LCS_最长公共子串变形

代码很容易写出来。

可是，不看题解，根本想不到这思路，咋就想出了这是LCS的变形问题呢

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        String str=reader.readLine();
        String strb=(new StringBuffer(str)).reverse().toString();
        int len=process2(str,strb);
        System.out.println(str.length()-len);


        reader.close();
    }

    public static int process2 (String a,String b){
        int[] up=new int[a.length()+1];
        int[] current=new int[a.length()+1];
        for (int i = 1; i <=b.length() ; i++) {//取出一个b和a的每个字母进行比较
            up=current;
            current=new int[a.length()+1];
            for (int j = 1; j <=a.length() ; j++) {//取出a的每一个字母
                if(b.charAt(i-1)==a.charAt(j-1)){//相等，取左上方+1
                    current[j]=up[j-1]+1;
                }else{//两个不相等，取左边或者上面最大的一个
                    current[j]=Math.max(Math.max(current[j-1],up[j]),up[j-1]);
                }

            }
            //System.out.println(Arrays.toString(current));
        }
        return current[current.length-1];
    }

}