dp

设f[i][j]为[0,i] [0,j]中能够成公共子序列的最大值
f[i][j] = max(f[i - 1][j],f[i][j - 1],f[i - 1][j - 1] + (s[i] == s[j]))

import java.util.*;


public class Solution {
    public String LCS (String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int f[][] = new int[n + 10][m + 10];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                f[i + 1][j + 1] = Math.max(f[i + 1][j],f[i][j + 1]);
                if(s1.charAt(i) == s2.charAt(j)){
                    //System.out.println("in");
                    if(f[i + 1][j + 1] < f[i][j] + 1){
                        f[i + 1][j + 1] = f[i][j] + 1;
                    }
                }
            }
        }
        StringBuffer ret = new StringBuffer("");
        boolean ok = true;
        for(int i = n - 1,j = m - 1;f[i + 1][j + 1] >= 1;){
            if(s1.charAt(i) == s2.charAt(j)){
                ret.append(s1.charAt(i));
                i--;j--;
                ok = false;
            }else if(f[i + 1][j] < f[i][j + 1])i--;
            else j--;
        }
        if(ok)return "-1";
        return ret.reverse().toString();
    }
}