NC92 #最长公共子序列#

第一步，通过动态规划找到最长公共子序列长度，并构建dp数组：
dp[i][j]:s1[i]和s2[j]为止的最长公共子序列的长度。
dp[0][0] = s1[0] == s2[0]
dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0]
dp[0][i] = s1[0] == s2[i] ? 1 : dp[0][i - 1]
dp[i][j] = dp[i - 1][j - 1] + 1, s1[i] == s2[j]
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]), s1[i] != s2[j]

第二步，根据dp反推最长公共子序列内容。

class Solution {
public:
    string LCS(string s1, string s2) {
        if(s1.empty() || s2.empty()) return "-1";
        int len1 = s1.size(), len2= s2.size();
        int dp[len1][len2];
        dp[0][0] = s1[0] == s2[0];
        for(int i = 1; i < len1; i++)
                dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0];
        for(int i = 1; i < len2; i++)
                dp[0][i] = s1[0] == s2[i] ? 1 : dp[0][i - 1];
        for(int i = 1; i < len1; i++)
        {
            for(int j = 1; j < len2; j++)
            {
                if(s1[i] == s2[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        string ans = "";
        for(int i = len1 - 1, j = len2 - 1; i >= 0 && j >= 0;)
        {
            if(s1[i] == s2[j])
            {
                ans += s1[i];
                i--, j--;
            }
            else if(j == 0 || dp[i - 1][j] > dp[i][j - 1]) i--;
            else if(i == 0 || dp[i][j - 1] >= dp[i - 1][j]) j--;
        }
        reverse(ans.begin(), ans.end());
        return ans.size() == 0 ? "-1" : ans;
    }
};