package?basic.dp;

/**
?*?動態規劃，找出《所有》最長公共子序列
?*?
?*?@description?LongestCommonSubSequence.java
?*?@author?Administrator
?*?@date?2018/04/17
?*?@version
?*/

public?class?LongestCommonSubSequence?{
	public?static?void?main（String[]?args）?{
		String?x?=?“ABCBDAB“;
		String?y?=?“BDCABA“;
		
		int?longest?=?getLCS（x?y）;
		//System.out.println（longest）;
	}

	/**
	?*?getLCS?TODO?:得到最長子序列長度，并輸出所有最長子序列
	?*?
	?*?@param?x
	?*????????????序列x
	?*?@param?y
	?*????????????序列y
	?*?@return?最長子序列長度
	?*?@author?zhiman
	?*?@date?2018/04/17?下午9:24:18
	?*/
	private?static?int?getLCS（String?x?String?y）?{
		int?xlen?=?x.length（）;
		int?ylen?=?y.length（）;

		//?此處的棋盤長度要比字符串長度多加1，需要多存儲一行0和一列0
		int[][]?commonSublen?=?new?int[xlen?+?1][ylen?+?1];
		//?1代表上?2?代表向左上?3代表向左?4代表上或者左
		int[][]?direction?=?new?int[xlen?+?1][ylen?+?1];
		//?將整個數組commonSublen填充值
		for?（int?i?=?1;?i?<=?xlen;?i++）?{
			char?xi?=?x.charAt（i?-?1）;
			for?（int?j?=?1;?j?<=?ylen;?j++）?{
				char?yj?=?y.charAt（j?-?1）;
				if?（xi?==?yj）?{
					commonSublen[i][j]?=?commonSublen[i?-?1][j?-?1]?+?1;
					//?2?代表向左上
					direction[i][j]?=?2;
				}?else?if?（commonSublen[i?-?1][j]?>?commonSublen[i][j?-?1]）?{
					commonSublen[i][j]?=?commonSublen[i?-?1][j];
					//?1代表上
					direction[i][j]?=?1;
				}?else?if?（commonSublen[i?-?1][j]?					commonSublen[i][j]?=?commonSublen[i][j?-?1];
					//?3代表左
					direction[i][j]?=?3;
				}?else?{
					//?如果commonSublen[i?-?1][j]?==?commonSublen[i][j?-?1]
					//?向上或者向左不影響結果
					//?4代表上?或者?左
					commonSublen[i][j]?=?commonSublen[i?-?1][j];
					//?1代表上
					direction[i][j]?=?4;
				}