#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1011;
int dp[Maxn][Maxn];
int main(){
string A,B;
cin >> A >> B;
int a = A.length(),b = B.length();
int maxn = -1;
for( int i = 1; i <= A.length(); i++ ){
for( int j = 1; j <= B.length(); j++ ){
if( A[i-1] == B[j-1] ){
dp[i][j] = dp[i-1][j-1]+1;
}else if( dp[i][j-1] > dp[i-1][j] ){
dp[i][j] = dp[i][j-1];
}else{
dp[i][j] = dp[i-1][j];
}
maxn = max( maxn,dp[i][j] );
}
}
vector<char> v;
for( int i = a,j = b; i >= 1 && j >= 1; ){
if( A[i-1] == B[j-1] ){
v.push_back(A[i-1]);
i--,j--;
}else{
if( dp[i][j-1] > dp[i-1][j] ){
j--;
}else{
i--;
}
}
}
reverse(v.begin(),v.end());
for(auto x:v){
cout << x;
}
}
用python实现了一下,吐血了,一个浅拷贝弄得我要死
python定义数组不可以用dp = [[0]*1010]*1010,会有浅拷贝,具体的可以百度一下
下面是python的代码
dp = [([0]*1010) for i in range(1010)]
A = list(raw_input())
B = list(raw_input())
a = len(A)
b = len(B)
for i in range(1,a+1):
for j in range(1,b+1):
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] )
val = []
i = a
j = b
while i >= 1 and j >= 1:
if A[i-1] == B[j-1]:
val.append(A[i-1])
i -= 1
j -= 1
else:
if dp[i][j-1] > dp[i-1][j]:
j -= 1
else:
i -= 1
print "".join(val[::-1])