线性DP·最长公共子序列标准题解

#include <iostream>
using namespace std;
const int N=1005;
string s,t;
//两个字符串

int dp[N][N];
//dp数组

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //增加输入速度
    
    cin>>s>>t;
    int n=s.size();
    int m=t.size();
    //n,m变量简化字符串长度,便于字符串和dp数组的遍历

    /*
    
    对于dp[x][y]:
    
    1. x(下标)表示在字符串s中的第x个字符
    
    2. y(下标)表示在字符串t中的第y个字符

    3. dp[x][y]表示:
    
       以字符串s中以第x个字符为结尾时的字符串与
       以字符串t中以第y个字符为结尾时的字符串的 最大公共子序列长度 

        */

    /*
    
      众所周知,dp[0][0]=dp[i][j]=0
      初始化都是0
      
        */
    
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (s[i-1]==t[j-1]){
                dp[i][j]=dp[i-1][j-1]+1; 
                //如果对当前的i,j,字符串s的第i个字符和字符串t中第j个字符相等,则更新dp比上一组多1个单位长度
                
            }
            else {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                //如果不相等则进行dp更新
                
            }
        }
    }
    cout<<dp[n][m];
    //输出最终的LIS
    
    return 0;
}