最长公共子序列之求出所有子序列java源代码（回溯+动态规划）_找出动态规划数组的所有相同长度的序列 java

package suanfa;
 
import java.util.ArrayList;
import java.util.List;
 
public class LongestCommonSubsequence {
	static int[][] dp;
	static 	List<String> x = new ArrayList<String>();
	public static void main(String[] args) {
		int k=longestCommonSubsequence("ABCBDAB", "BDCABA");
		 traceBack(7, 6, "", "ABCBDAB", "BDCABA", dp);
		System.out.println(k);
		for(String s : x) {
			System.out.println(s);
		}
	}
	public static int longestCommonSubsequence(String text1, String text2) {
	      dp=new int[text1.length()+1][text2.length()+1];
          
	      for(int i=1;i<dp.length;i++){
 
	          for(int j=1;j<dp[0].length;j++){
	              if(text1.charAt(i-1)==text2.charAt(j-1)){
	                  dp[i][j]=dp[i-1][j-1]+1;
	                  
	                  
	              }else{
	                  dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
	              }
	          }
	      }
	     
	      return dp[text1.length()][text2.length()];
	    }
	private static void traceBack(int i, int j, String lcs_str,String t1,String t2,int[][] dp) {
		while (i>0 && j>0) {
			if (t1.charAt(i-1) == t2.charAt(j-1)) {
				lcs_str += t1.charAt(i-1);
				--i;
				--j;
			}
			else {
				if (dp[i-1][j]> dp[i][j-1])
					--i;
				else if (dp[i-1][j] < dp[i][j-1])
					--j;
				else {  // 相等的情况
					traceBack(i-1, j, lcs_str,t1,t2,dp);
					traceBack(i, j-1, lcs_str,t1,t2,dp);
					return;
				}
			}
		}
		x.add(lcs_str);
	}
}