C++14(g++5.4) 解法, 执行用时: 10ms, 内存消耗: 4296K, 提交时间: 2018-12-02 14:38:46

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int c[1010][1010];
int main()
{
	string a,b;
	cin>>a>>b;
	int la=a.length(),lb=b.length(),i,j;
	for( i=1;i<=la;i++)
	{
		for( j=1;j<=lb;j++)
		{
			if(a[i-1]==b[j-1])
			c[i][j]=c[i-1][j-1]+1;
			else
			c[i][j]=max(c[i-1][j],c[i][j-1]);
		}
	}
	cout<<c[la][lb]<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 4300K, 提交时间: 2020-03-16 21:05:53

#include<iostream>
#include<string>
using namespace std;
int dp[1010][1010];
int main()
{
	string a,b;
	cin>>a>>b;
	int l1=a.length(),l2=b.length();
	for(int i=1;i<=l1;i++)
	for(int j=1;j<=l2;j++)
	if(a[i-1]==b[j-1])
	dp[i][j]=dp[i-1][j-1]+1;
	else
	dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
	cout<<dp[l1][l2]<<endl;
}

Python3(3.5.2) 解法, 执行用时: 1540ms, 内存消耗: 12056K, 提交时间: 2020-02-24 20:54:08

s1 = input()
s2 = input()
l1,l2 = len(s1),len(s2)
M = [[0]*(l2+1) for i in range(l1+1)]
for i in range(l1):
    for j in range(l2):
        a = 1 if s1[i]==s2[j] else 0
        M[i+1][j+1] = max([M[i][j]+a, M[i][j+1], M[i+1][j]])
print(M[l1][l2])