最长公共子序列

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

        if (s1.length() == 0 || s2.length() == 0) return "-1";

        int m = s1.length();
        int n = s2.length();

        int[][] dp = new int[m + 1][n + 1];
        // 标识该结果是由哪个方向转变的
        // 1 dp[i - 1][j - 1]
        // 2 dp[i - 1][j]  上方
        // 3 dp[i][j - 1] 左方
        int[][] dir = new int[m + 1][n +1]; 

        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    dir[i][j] = 1;
                } else {
                    if (dp[i - 1][j] >= dp[i][j - 1]) {
                        dp[i][j] = dp[i - 1][j]; // 上方
                        dir[i][j] = 2;
                    } else {
                        dp[i][j] = dp[i][j - 1]; // 左方
                        dir[i][j] = 3;
                    }
                }
            }
        }    

        int i = m, j = n;
        StringBuilder sb = new StringBuilder();

        // 从后往前遍历，根据转变的方向添加正确的字符，最后反转输出即可
        while (i >= 0 && j >= 0) {
            if (dir[i][j] == 1) {
                i --;
                j --;
                sb.append(s1.charAt(i));
            } 
            else if (dir[i][j] == 2) i --;
            else j --;
        }
        return sb.length() > 0 ? sb.reverse().toString() : "-1";
    }
}

思路：
先创建一个二维数组 dp，保存字符串 s1(0 -> i) 和 s2(0 -> j) 的最长公共子序列长度
在创建一个二维数组 dir, 表示 dp 数组值发生变化是，值是由 dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1]变化而来的。

遍历字符串 s1、s2，当 s1.charAt(i - 1) == s2.charAt(j - 1) 时，最长公共子序列长度 + 1，dir[i][j] = 1;
当 s1.charAt(i - 1) != s2.charAt(j - 1) 时，若 dp[i - 1][j] >= dp[i][j - 1], 则说明上面的值比下面的值大，
dp[i][j] = dp[i - 1][j], dir[i][j] = 2; 否则说明左边的值比上方的值大，dir[i][j] = 3。

最后从后往前遍历字符串，根据字符串转变的方向将之添加入结果中，最后将结果反转输出即可。