密碼脫落 （最長公共子序列+非連續）

X星球的考古學家發現了一批古代留下來的密碼。

這些密碼是由A、B、C、D 四種植物的種子串成的序列。

仔細分析發現，這些密碼串當初應該是前後對稱的（也就是我們說的鏡像串）。

由于年代久遠，其中許多種子脫落了，因而可能會失去鏡像的特征。

你的任務是：

給定一個現在看到的密碼串，計算一下從當初的狀态，它要至少脫落多少個種子，才可能會變成現在的樣子。

輸入一行，表示現在看到的密碼串（長度不大于1000）

要求輸出一個正整數，表示至少脫落了多少個種子。

例如，輸入：

ABCBA

則程式應該輸出：

再例如，輸入：

ABDCDCBABC

則程式應該輸出：

3

資源約定：

峰值記憶體消耗（含虛拟機） < 256M

CPU消耗  < 3000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入...” 的多餘内容。

所有代碼放在同一個源檔案中，調試通過後，拷貝送出該源碼。

注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。

注意：主類的名字必須是：Main，否則按無效代碼處理。

題意：最初一個串是回文串，求：給一個串，加上多少個字母變成最初串（即：回文串）；

題解：用給出串的長度減去給出串與反轉串的最長公共子序列（非連續），一下用兩種方法，即：一維(相當于一維)的和二維的。

一維(相當于一維)：

import java.util.*;
public class Main {
    static Scanner cin = new Scanner(System.in);
    static String s1,s2;
    static int [][] dp = new int [2][1111];//相當于一維昂~~
    public static void main(String[] args){
    	s1=cin.next();
    	s2=new StringBuffer(s1).reverse().toString();//字元串反轉
    	int len=s1.length();
    	for (int i = 1; i <= len;i++) {//求最長公共子序列，(非連續)
    		for (int j = 1; j <= len;j++) {
    			if(s1.charAt(i-1)==s2.charAt(j-1)) dp[i%2][j]=dp[(i-1)%2][j-1]+1;
    			else dp[i%2][j]=Math.max(dp[i%2][j-1], dp[(i-1)%2][j]);
    		}
    	}
    	System.out.println(len-dp[len%2][len]);//用給出串的長度減去給出串與反轉串的最長公共子序列（非連續）
    }
}           

二維：

import java.util.*;
public class Main {
    static Scanner cin = new Scanner(System.in);
    static String s1,s2;
    static int [][] dp = new int [1111][1111];
    public static void main(String[] args){
    	s1=cin.next();
    	s2=new StringBuffer(s1).reverse().toString();//字元串反轉
    	int len=s1.length();
    	for (int i = 1; i <= len;i++) {//求最長公共子序列，(非連續)
    		for (int j = 1; j <= len;j++) {
    			if(s1.charAt(i-1)==s2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
    			else dp[i][j]=Math.max(dp[i][j-1], dp[i-1][j]);
    		}
    	}
    	System.out.println(len-dp[len][len]);//用給出串的長度減去給出串與反轉串的最長公共子序列（非連續）
    }
}