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

解题思路：

• 利用dp[i][j]表示以s1以i为结尾的子串，s2以j为结尾的子串中有最长的公共子序列的长度，那么普遍情况$i!=0andj!=0i\backslash \; !=\backslash \; 0\backslash \; and\backslash \; j\backslash \; !=\backslash \; 0$时最长公共子串的长度要么是从$dp[i-1][j-1]+s1[i]==s2[j]dp[i-1][j-1]\; +\; s1[i]==s2[j]$而来，要么是从$dp[i-1][j]dp[i-1][j]$而来，要么是从$dp[i][j-1]dp[i][j-1]$而来，只要取三者最大值即可。
• 特殊处理 当$dp[0][0]=s1[0]==s2[0]dp[0][0]\; =\; s1[0]\; ==\; s2[0]$,当 i=0 时，$dp[0][j]=max(dp[0][j-1],s1[0]==s2[j])dp[0][j]\; =\; max(dp[0][j-1],s1[0]\; ==\; s2[j])$--最大长度只可能是1， 当j = 0时，$dp[i][0]=max(dp[i-1][0],s1[i]==s2[0])dp[i][0]\; =\; max(dp[i-1][0],\; s1[i]\; ==\; s2[0])$--最大长度只可能是1.
• 使用空间压缩满足空间使用复杂度为$O{(}_{min}(n,m))O(\_\{min\}(n,m))$,dp的值只和上一轮dp有关，则可以存储上一轮dp，进而取代二维数组。

#include<bits/stdc++.h>
using namespace std;
int solve(string &s1, string &s2, int i, int j, vector<vector<int>> &dp){ //递归
    if(dp[i][j] != -1) return dp[i][j];
    if(i == 0 && j == 0) dp[i][j] = s1[i] == s2[j];
    else if(i == 0) dp[i][j] = max(solve(s1,s2,i,j-1,dp), (int)(s1[0] == s2[j]));
    else if(j == 0) dp[i][j] = max(solve(s1,s2,i-1,j,dp), (int)(s1[i] == s2[j]));
    else{
        dp[i][j] = max(solve(s1,s2,i-1,j-1,dp)+(s1[i] == s2[j]), max(solve(s1,s2,i,j-1,dp), solve(s1,s2,i-1,j,dp)));
    }
    return dp[i][j];
}
int solve2(string &s1, string &s2, int n, int m, vector<vector<int>> &dp){ //递推
    dp[0][0] = s1[0] == s2[0];
    for(int i = 1; i < n; ++i){
        dp[i][0] = max(dp[i-1][0], (int)(s1[i] == s2[0]));
    }
    for(int j = 1; j < m; ++j){
        dp[0][j] = max(dp[0][j-1], (int)(s1[0] == s2[j]));
    }
    for(int i = 1; i < n; ++i){
        for(int j = 1; j < m; ++j){
            dp[i][j] = max(max(dp[i-1][j-1] + (s1[i] == s2[j]),dp[i-1][j]),dp[i][j-1]);
        }
    }
    return dp[n-1][m-1];
}
int solve3(string &s1, string &s2, int n, int m){
    //启用一个暂存，来存储dp迭代中上一次的状态。这样两个交替轮换就可以压缩空间。
    //这里在dp中多补了一个位置，用于统一地处理边界问题，而不再需要特判i = 0，j = 0
    //自踩坑点，使用了字符串指针来交换两个字符串。然后得到了段错误 
     vector<int> dp(n+1);
     vector<int> prev_dp(n+1); //暂存，用于存储上一轮的dp值
     for(int i = 1; i <= m; ++i){
         for(int j = 1; j <= n; ++j){
             if(s1[j-1] == s2[i-1]) dp[j] = prev_dp[j-1] + 1;
             else dp[j] = max(dp[j-1], prev_dp[j]);
         }
         for(int j = 1; j <= n; ++j) prev_dp[j] = dp[j];
     }
     return dp[n];
}
int main(){
    int n, m;
    cin>>n>>m;
    string s1, s2;
    cin>>s1;
    cin>>s2;
    vector<vector<int>> dp(n, vector<int>(m, -1));
    // cout<<solve(s1, s2, n-1, m-1, dp)<<endl;
    // cout<<solve2(s1, s2, n, m, dp)<<endl;
    if(n>m){
        swap(s1, s2);
        swap(n,m);
    }
    cout<< solve3(s1, s2, n, m)<<endl;
    return 0;
}