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

W:
dp[i][j]表示s1,s2在i-1,j-1之前最长公共子序列的长度;
熟悉这个定义后容易得到如果字符串相等,那么dp[i][j] = dp[i - 1][j - 1] + 1;
如果不相等,那么需要做出选择,当前状态是由两个字符串转换而来,即s1[...i-2]与s2[...j-1或s2[...j-2]与s1[...i-1]对应dp[i-1][j]和dp[i][j-1]
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

反向遍历参考

N
i <= len1中的"=";
反向遍历相等情况
dp[i - 1][j] >= dp[i][j - 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)
    {
        // write code here
        const int len1 = s1.size(), len2 = s2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        string res = "";
        for (int i = 1; i <= len1; i++)
        {
            for (int j = 1; j <= len2; 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], dp[i][j - 1]); // note
                }
            }
        }
        for (int i = len1, j = len2; dp[i][j] >= 1;)
        {
            if (s1[i - 1] == s2[j - 1])
            {
                res += s1[i - 1];
                i--;
                j--; //根据递推公式可得
            }
            else
            {
                if (dp[i - 1][j] >= dp[i][j - 1])
                    i--; //说明当前最大是由左边转换而来的
                else
                {
                    j--;
                }
            }
        }
        reverse(res.begin(), res.end());
//         return res;需要判断是否为空
        return res.empty()? "-1":res;
    }
};