题解 | #最长公共子序列-II#

思路：动态规划，有一个朋友讲的特别详细，可以去参考下，相信一定会有收获。
csdn地址：https://blog.csdn.net/hrn1216/article/details/51534607

public String LCS (String s1, String s2) {
        // write code here
        StringBuilder sb=new StringBuilder();
        int len1=s1.length();
        int len2=s2.length();
        int[][] dp=new int[len1+1][len2+1];
        //初始化dp数组
        for(int i=0;i<len1+1;i++){
            dp[i][0]=0;
        }
        for(int j=0;j<len2+1;j++){
            dp[0][j]=0;
        }
        //求解dp数组
        for(int i=1;i<len1+1;i++){
            for(int j=1;j<len2+1;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-1][j],dp[i][j-1]);
                }
            }
        }
        //若没有公共子序列，返回-1
        if(dp[len1][len2]==0){
            return "-1";
        }
        //反向寻找路线
        int index1=len1;
        int index2=len2;
        while(dp[index1][index2]!=0 && index1>0 && index2>0){
            if(s1.charAt(index1-1)==s2.charAt(index2-1)){
                sb.append(s1.charAt(index1-1));
                index1--;
                index2--;
            }else{
                if(dp[index1][index2-1]>dp[index1-1][index2]){
                    index2--;
                }
                else{
                    index1--;
                }
            }
        }
        //由于是倒着寻找，需要再反转一下。
        return sb.reverse().toString();
    }