这个题的很多解法是将dp数组变为int类型来计算的，所以是按照最长公共子序列（一）的思路来实现的，然后在通过长度从尾巴遍历得到结果。其实这样会比较麻烦，我们可以在设置dp数组的时候就把其设置为String类型的。求出的dp就是我们要的结果，也就不需要去遍历求解了。 
import java.util.*;


public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // write code here
        char[] c1=s1.toCharArray();
        char[] c2=s2.toCharArray();
        int len1=s1.length();
        int len2=s2.length();
        String[][] dp=new String[len1+1][len2+1];
        for(int i=0;i<=len1;i++){
            dp[i][0]="";
        }
        for(int i=0;i<=len2;i++){
            dp[0][i]="";
        }
        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] + c2[j-1];
                }else if(dp[i-1][j].length()>dp[i][j-1].length()){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i][j-1];
                }
            }
        }
        return dp[len1][len2].length()==0?"-1":dp[len1][len2];
    }
}