题解 | #最长公共子序列(二)#

思路：

设状态dp[i][j] = s1[0...i-1]和s2[0...j-1]的最长公共子序列

状态转移方程从下面两个方面可以推出：

1. 当s1[i-1]==s2[j-1]，即两个子字符串的最后一位字符相同时，此时最长的公共子序列应该把当前字符加入，即 = 同时去掉该相同字符 s1[i-2]==s2[j-2]的最长公共子序列 + 字符s1[i-1]

2. 当s1[i-1]!=s2[j-1]，即两个子字符串的最后一位字符不相同时，此时最长公共子序列应该寻找 去掉s1的最后一位字符，s1[i-2]与s2[j-1]的最长公共子序列 与 去掉s2的最后一位字符，s1[i-1]与s2[j-2]的最长公共子序列 的最长那个

初始条件：任一字符串与空串的最长公共子序列长度都空串

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) {
        // 任一为空串，直接返回
        if(s1.length()==0 || s2.length()==0) return "-1";
        
        int m = s1.length();
        int n = s2.length();
        
        String[][] dp = new String[m+1][n+1];
        
        //初始化: 任一字符串与空串的最长公共子序列长度都空串
        for(int i=0; i<=m; i++) dp[i][0] = "";
        for(int j=0; j<=n; j++) dp[0][j] = "";
        
        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] + s1.charAt(i-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[m][n].length()!=0? dp[m][n] : "-1";
    }
}