#include<bits/stdc++.h>
using namespace std;
const int N=3010;
char s1[N],s2[N],s[1100];
int f[N][N];
struct node
{
    int x,y;
}root[N][N];
int main()
{
    scanf("%s",s1+1);int n1=strlen(s1+1);
    scanf("%s",s2+1);int n2=strlen(s2+1);
     
    memset(f,0,sizeof(f));
      
    for(int i=1; i<=n1;i++)
        for(int j=1;j<=n2;j++)
            if(s1[i]==s2[j])
            {
                f[i][j]=f[i-1][j-1]+1;
                root[i][j].x=i;root[i][j].y=j; 
            }
            else
            {
                if(f[i][j-1]>f[i-1][j])
                {
                    f[i][j]=f[i][j-1];
                    root[i][j]=root[i][j-1]; 
                }
                else
                {
                    f[i][j]=f[i-1][j];
                    root[i][j]=root[i-1][j]; 
                }
            }
      
    int x=root[n1][n2].x;
    int y=root[n1][n2].y;
    int n=0;
    while(f[x][y]>0)
    {
        s[++n]=s1[x];
        x--;y--;
        int tx=root[x][y].x;
        int ty=root[x][y].y;
        x=tx;y=ty;
    }
    for(int i=n;i>=1;i--) printf("%c",s[i]);
    printf("\n");
    return 0;
}

一眼动态规划， 我们用 $dp[i][j]$ 表示 $s$[1~i] 与 $t$[1~j] 的最长公共子序列(字符串)，剩下的很好想，不会的去看以前的dp题目 , 根据这个转换一下思路，就可以推出来动态转移方程了。

AC代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=3100;
//朴素dp
int dp[N][N];
string d[N][N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	string s,t;
	cin>>s>>t;
	int n=s.size(),m=t.size();
	s='@'+s;
	t='@'+t;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i]==t[j]){
				dp[i][j]=dp[i-1][j-1]+1;
				d[i][j]=d[i-1][j-1]+s[i];
			}
			if(dp[i][j]<dp[i-1][j]){
				d[i][j]=d[i-1][j];
				dp[i][j]=dp[i-1][j];
			}
			if(dp[i][j]<dp[i][j-1]){
				d[i][j]=d[i][j-1];
				dp[i][j]=dp[i][j-1];
			}
		}
	}
	cout<<d[n][m];
	return 0;
}

被骗了吧

骗你的，其实RE，只有50分。

因为 $s,t\leq3000$ , 且空间复杂度为 $O(n^3)$ ， 则最大内存约为 $3000^3 = 27,000,000,000$ 字节 ， 约为 $25750$ MB , 严重超限。

众所周知 也可能不周知 动态规划中有个叫 滚动优化 的东东，它通过是用来减少动态规划数组维度的，这样就能程序不必要的空间。

我们可以减少一维，那么我们就要想办法表示我们所需的变量，用字符串pre表示dp[i-1][j-1] ， 剩下的就好解决了。

这个是真正的 AC 代码！！！

#include<bits/stdc++.h>
using namespace std;
constexpr int N=3010;
//动态规划 
/*
二维数组内存会超限，
所以进行滚动优化，
优化成一维数组 
*/ 
string dp[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string s,t;
    cin>>s>>t;
    int n=s.size(),m=t.size();
    s=' '+s,t=' '+t;//使字符串从下标1开始 
    for(int i=1;i<=n;i++){//遍历字符串s 
        string pre=dp[0];//表示s[1~i-1],t[1~j-1]的最长公共子序列 
        for(int j=1;j<=m;j++){//遍历字符串t 
            string temp=dp[j];//s[1~i-1],t[1~j-1]的最长公共子序列 
            if(s[i]==t[j]){//当前对应位置相等 
                if(pre.size()+1>dp[j].size()){ 
                    dp[j]=pre+s[i];
                }//选择当前最长公共子序列
            }
            if(dp[j-1].size()>dp[j].size()){
                dp[j]=dp[j-1];
            }//选择当前最长公共子序列 
            pre=temp;//记录s[1~i],t[1~j]的最长公共子序列，作为下一轮的dp[i-1][j-1]
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
char s1[N],s2[N],s[1100];
int f[N][N];
struct node
{
    int x,y;
}root[N][N];
int main()
{
    scanf("%s",s1+1);int n1=strlen(s1+1);
    scanf("%s",s2+1);int n2=strlen(s2+1);
     
    memset(f,0,sizeof(f));
      
    for(int i=1; i<=n1;i++)
        for(int j=1;j<=n2;j++)
            if(s1[i]==s2[j])
            {
                f[i][j]=f[i-1][j-1]+1;
                root[i][j].x=i;root[i][j].y=j; 
            }
            else
            {
                if(f[i][j-1]>f[i-1][j])
                {
                    f[i][j]=f[i][j-1];
                    root[i][j]=root[i][j-1]; 
                }
                else
                {
                    f[i][j]=f[i-1][j];
                    root[i][j]=root[i-1][j]; 
                }
            }
      
    int x=root[n1][n2].x;
    int y=root[n1][n2].y;
    int n=0;
    while(f[x][y]>0)
    {
        s[++n]=s1[x];
        x--;y--;
        int tx=root[x][y].x;
        int ty=root[x][y].y;
        x=tx;y=ty;
    }
    for(int i=n;i>=1;i--) printf("%c",s[i]);
    printf("\n");
    return 0;
}