题解 | #最长公共子序列-II#

题目

题解：动态规划，dp[i][j]表示s1字符串中第i个字符结尾和s2字符串中第j个字符结尾时的最长公共子序列，如果s1[i]==s2[j]，则dp[i][j]=dp[i-1][j-1]+s1[i]，否则取dp[i][j]=max(dp[i-1][j],dp[i][j-1)]。又因为dp只和上一行有关系，所以只需要2行即可

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
        int size1=s1.size(),size2=s2.size();
        vector<vector<string>>dp(2,vector<string>(size2+1,""));//定义2*(size2+1)维度的字符串数组
        //dp[i][0]和dp[0][j]是""空字符串
        int row=1;
        for(int i=0;i<size1;i++)
        {
            row=1-row;//row是上一行,1-row是当前行
            for(int j=0;j<size2;j++)
            {
                //dp[row][j]是上一行前一列的字符串，dp[row][j+1]是上一行的字符串，dp[1-row][j]是当前行前一列字符串
                dp[1-row][j+1]=s1[i]==s2[j]?dp[row][j]+s1[i]:dp[row][j+1].size()>=dp[1-row][j].size()?dp[row][j+1]:dp[1-row][j];
            }
        }
        return dp[1-row][size2]==""?"-1":dp[1-row][size2];//返回当前行最后一列
    }
};