9
POJ1458 HDU1159 Common Subsequence（最长公共子序列 DP）
source link: https://arminli.com/poj1458/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
POJ1458 HDU1159 Common Subsequence（最长公共子序列 DP）
March 21, 2016
#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
char s1[1005];
char s2[1005];
int dp[1005][1005];
int main(){
//freopen("a.txt", "r", stdin);
while(~scanf("%s %s", s1+1, s2+1)){
memset(dp, 0, sizeof(dp));
s1[0] = ' ';s2[0] = ' ';
int l1 = strlen(s1)-1;
int l2 = strlen(s2)-1;
for(int i = 1; i <= l1; i++){
for(int j = 1; j <= l2; j++){
if(s1[i]==s2[j])
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;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK