动态规划

1、求出最长公共子序列的长度

		// dp[i][j] 表示 到s1的i ，s2的j时，目前的公共子序列长度
        int[][] dp = new int[len1+1][len2+1];
        //记录方向，返回序列，用1表示来自左上方，2表示来自左边，3表示来自上边。
        int[][] direction = new int[len1+1][len2+1];
        // 找出数组元素之间的关系式
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(c1[i-1] == c2[j-1]){
                        dp[i][j] = dp[i-1][j-1]+1; 
                        direction[i][j] = 1; //来自左上方
                }else{
                    if(dp[i-1][j]>dp[i][j-1]){
                        dp[i][j] = dp[i-1][j]; 
                        direction[i][j] = 3; //来自上方
                    }else{
                        dp[i][j] = dp[i][j-1]; 
                        direction[i][j] = 2; //来自左方
                    }
                }              
            }
        }

2、根据长度还原出公共子序列

		// 最长公共子序列的长度
		int maxLen = dp[len1][len2];
        if(maxLen == 0){
            return "-1";
        }
        char[] res = new char[maxLen];
        int index = maxLen-1;
        int i=len1,j=len2;
        while(i>=0&&j>=0&&index>=0){
            if(direction[i][j] == 1){
                res[index--] = c1[i-1];
                i--;
                j--;                
            }else if(direction[i][j] == 2){
                j = j-1;
            }else{
                i = i-1;
            }
        }
        return new String(res);