题解 | #最长公共子序列（二）#

这道题对我有点难度哈。

dp状态转移方程怎么确认？怎么根据dp状态转移进行字符串还原？

这道题的难点

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
  //  找出最长公共子序列长度，同时记录该路径（下标）
  //  两个难点，一个状态转移，一个字符串组装
    string LCS(string s1, string s2) {
      if (s1.empty() || s2.empty()) {
        return "-1";
      }
      
      int len_1 = s1.size(), len_2 = s2.size();
      //  二维dp，每个i j 代表长度为i j 的最大公共前缀
      //  长度达到 len_1 len_2 时达到题目要求
      std::vector<std::vector<int>> dp(len_1 + 1, std::vector<int>(len_2 + 1, 0));
      
      for (int i = 0; i < len_1; ++i) {
        for (int j = 0; j < len_2; ++j) {
          //  长度从1开始，0长度最大公共前缀必定为0，已默认初始化
          //  两个字符串长度同时增加一位，比较字符相等，则在前一相等（最大公共序列）长度上加一
          //  不等则取单个字符串长度加一中的最大值
          dp[i + 1][j + 1] = s1[i] == s2[j] ? dp[i][j] + 1 : std::max(dp[i][j + 1], dp[i + 1][j]);
        }
      }
      
      //  长度为原字符串长度时的最大公共序列
      if (dp[len_1][len_2] == 0) {
        return "-1";
      }
      
      //  组装最大公共序列（从后面回溯）
      std::string res;
      //  指向末尾
      len_1 -= 1;
      len_2 -= 1;
      
      //  到开头时结束
      while (len_1 >= 0) {
        //  两者相等，同时退一步
        if (s1[len_1] == s2[len_2]) {
          res += s1[len_1];
          len_1 -= 1;
          len_2 -= 1;
        //  不等，根据dp状态转移
        //  len + 1 指向的是当前长度，而不是多一位的长度，注意下标之间的差别
        } else if (dp[len_1 + 1][len_2] > dp[len_1][len_2 + 1]) {
          len_2 -= 1;
        } else {
          len_1 -= 1;
        }
      }
      
      //  从后往前组装，是逆序
      std::reverse(res.begin(), res.end());
      
      return res;
    }
};