题解 | #最长公共子序列-II#(动态规划且得到字符串结果)

1. dp[i][j]：str1中以第i位置结尾和str2中以第j个位置结尾的两个字符的最长公共子序列
2. 初始化：dp[i][0]和dp[0][j] 因为某一个字符串0位置没有长度所以公共长度为0
3. 
4. 根据dp，从后往前，查找结果。

class Solution {
    /*
    dp[i][j]：str1中以第i位置结尾和str2中以第j个位置结尾的两个字符的最长公共子序列
    初始化：dp[i][0]和dp[0][j] 因为某一个字符串0位置没有长度所以公共长度为0
    dp[i][j] =  dp[i-1][j-1] + 1   当(s1[i-1] == s2[j-1])时。
            max(dp[i-1][j], dp[i][j-1]);  others
    根据dp，从后往前，查找结果。
    */
public:
    string LCS(string s1, string s2) {
        if(s1.empty() || s2.empty()) return "-1";  // 边界
        int dp[s1.size()+1][s2.size()+1]; // dp数组
        // 初始化
        for(int i = 0; i <= s1.size(); i++) 
            dp[i][0] = 0;
        for(int j = 0; j <= s2.size(); j++) 
            dp[0][j] = 0;
        for(int i = 1; i <= s1.size(); i++) {
            for(int j = 1; j <= s2.size(); j++) 
                dp[i][j] = (s1[i-1] == s2[j-1]) ? dp[i-1][j-1] + 1: max(dp[i-1][j], dp[i][j-1]); 
        }
        string res = "";
        for(int i = s1.size(), j = s2.size(); 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.empty() ? "-1" : res;
    }
};