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

最优子结构：dp[i][j]表示字符串s1第i位为结尾和字符串s2第j位为结尾的最长公共子序列的长度

#include <algorithm>
#include <iostream>
#include <vector>
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
        if (s1.empty() || s2.empty()) {
            return "-1";
        }
        //初始化dp,dp表示长度
        vector<vector<int>> dp(s1.size()+1,vector<int>(s2.size()+1,0));
        for (int i=0; i<s1.size()+1; i++) {
            dp[i][0] =0;
        }
        for (int j=0; j<s2.size()+1; j++) {
            dp[0][j] =0; 
        }
        //遍历顺序
        for (int i=1; i<s1.size()+1; i++) {
            for (int j=1; j<s2.size()+1; j++) {
                if (s1[i-1] == s2[j-1]) {//转态转移方程
                    dp[i][j] = dp[i-1][j-1] +1;
                    cout<<i<<j<<endl;
                    cout<<dp[i][j];                
                }else {
                    dp[i][j] = 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());
        cout<<res;
        cout<<res.size();
        return res.empty()?"-1":res;
    }
};