【入门DP】最长公共子序列_a subsequence of a given sequence is the given…

Description

Input

Output

Sample Input

abcfbc         abfcab
programming    contest 
abcd           mnp

Sample Output

4
2
0

题意：给定两组字符串，要求找出最长公共子序列。要求字母必须相同，且在各自的序列中位置   顺序相同。

找状态方程：(注意:)当都为0时候是不存在序列的，所以至少为1才能计算；

   因此有两种状态：

 如果前i项的字母和前j项的字母序列相同 ：dp[i][j] = d[i-1][j-1] + 1 ;

    否则  dp[i][j] = max (dp[i-1][j] , dp[i][j-1] ) ;

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std ;
int dp[1000][1000] ;
char str1[1100] , str2[1100];
int main()
{
	while(cin>>str1>>str2)
	{
		int len1 = strlen(str1);
		int len2 = strlen(str2);
		for(int i = 0 ; i<=len1;i++)
		{
			dp[i][0] = 0 ;
		}
		for(int i = 0 ; i<=len2;i++)
		{
			dp[0][i] = 0 ;
		}
		for(int i = 1 ; i <=len1 ;i++)
		{
			for(int j = 1; j<=len2 ; j++)
			{
				if(str1[i-1]==str2[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[len1][len2]<<endl;
	}
	return 0 ;
}