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

动态规划可以求出最长公共子序列的长度，dp[i][j]表示以i-1结尾的s1和以j-1结尾的s2之间的最长公共子序列长度，由dp[i-1][j]、dp[i][j-1]以及dp[i-1][j-1]这三个上一状态推导出当前状态。

难点在于如何根据dp表的信息得到具体的子序列。从dp的右下角到左上角方向遍历dp数组，途中首次遇到的s1[i-1]==s2[j-1]时的字符s1[i-1]就是公共子串中的字符。

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        int m=s1.size();
        int n=s2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1]));
            }
        }
        string result{};
        for(int i=m,j=n;dp[i][j]>=1;){
            if(s1[i-1]==s2[j-1]){
                result+=s1[i-1];
                i--;
                j--;
            }
            else if(dp[i-1][j]>=dp[i][j-1]) i--;
            else j--;
        }
        reverse(result.begin(),result.end());
        return result.empty()? "-1" : result;
    }
};