(POJ - 1458) common subsequence (longest common subsequence)

Topic link ：http://poj.org/problem?id=1458

The question ： Give you two strings at a time , Find the length of the longest common subsequence

This is a template problem for finding the longest common subsequence , This model is classic , Let me introduce the solution of this problem

This problem is solved by dynamic programming , set up dp[i][j] Represents the first string i Characters and the first... Of the second string j The length of the longest common subsequence of characters , Now let's start to analyze the state transition

If s1[i]==s2[j] that dp[i][j]=dp[i-1][j-1]+1（ The default is... In the first string i Characters and the second string Of the j Match characters ）

If not satisfied s1[i]==s2[j], that dp[i][j]=max(dp[i-1][j],dp[i-1][j]), How to understand this equation , Imagine , If dp[i][j] The last bit in the longest public string of the contained result corresponds to s1[m] and s2[n], Then it must be satisfied m!=i perhaps n!=j, because s1[i]！=s2[j], Now if n!=j Well , Then there must be dp[i][j-1]=dp[i][j], Because at this time, the second string j Characters do not belong to the characters in the longest common subsequence , So there is dp[i][j-1]=dp[i][j], Similarly, you can get if m!=i, At this time there is dp[i-1][j]=dp[i][j], therefore dp[i][j]=max(dp[i-1][j],dp[i-1][j])

At this time, some students may have doubts , Why to be s1[i]==s2[j] when dp[i][j]=dp[i-1][j-1]+1, Don't dp[i-1][j-1]+1>=max(dp[i-1][j],dp[i-1][j]), In fact, this inequality is true , According to our definition of state, we can get dp[i-1][j-1]+1>=dp[i-1][j] as well as dp[i-1][j-1]+1>=dp[i][j-1], Therefore, the above inequality will hold

The implementation is relatively simple , Here is the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1003;
char a[N],b[N];
int dp[N][N];//dp[i][j] Express a Middle front of string i Characters and b Middle front of string j The number of elements in the longest common subsequence of characters  
int main()
{
	while(scanf("%s%s",a+1,b+1)!=EOF)
	{
		int lena=strlen(a+1),lenb=strlen(b+1);
		for(int i=1;i<=lena;i++)
		for(int j=1;j<=lenb;j++)
		{
			if(a[i]==b[j])
				dp[i][j]=dp[i-1][j-1]+1;
			else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
		printf("%d\n",dp[lena][lenb]);
	}
	return 0;
}