HDU 1159 Common Subsequence 最长公共子序列

题意

给你两个字符串，求出这两个字符串的最长公共子序列，这里的子序列不一定是连续的，只要满足前后关系就可以。

解题思路

这个当然要使用动态规划了。

这里\(dp[i][j]\)代表第一个串的前\(i\)个字符和第二个串的前\(j\)个字符中最长的公共子序列的最长长度，递推关系如下：

优化：这里我们看到，每次的\(dp[i][j]\)的更新仅需要当前前一行\(dp[i-1][j-1]\)，\(dp[i-1][j]\)的值还有当前行的\(dp[i][j-1]\)的值，所以我们可以进行空间优化，开辟空间为\(dp[maxn][2]\)

代码实现

//带有空间优化的

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1005;

int dp[maxn][2];

char s1[maxn], s2[maxn];

int main()

{

	int len1, len2;

	while(scanf("%s %s", s1+1, s2+1)!=EOF)

	{

		memset(dp, 0, sizeof(dp));

		len1=strlen(s1+1);

		len2=strlen(s2+1);

		int flag=0;

		for(int i=1; i<=len1; i++)

		{

			for(int j=1; j<=len2; j++)

			{

				if(s1[i]==s2[j])

					dp[j][flag]=dp[j-1][!flag]+1;

				else

					dp[j][flag]=max(dp[j][!flag], dp[j-1][flag]);

			}

			flag=!flag;

		}

		printf("%d\n", dp[len2][!flag]);

	}

	return 0;

}

//没有空间优化的代码

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1005;

int dp[maxn][2];

char s1[maxn], s2[maxn];

int main()

{

	int len1, len2;

	while(scanf("%s %s", s1+1, s2+1)!=EOF)

	{

		memset(dp, 0, sizeof(dp));

		len1=strlen(s1+1);

		len2=strlen(s2+1);

		int flag=0;

		for(int i=1; i<=len1; i++)

		{

			for(int j=1; j<=len2; j++)

			{

				if(s1[i]==s2[j])

					dp[j][i%2]=dp[j-1][(i-1)%2]+1;

				else

					dp[j][i%2]=max(dp[j][(i-1)%2], dp[j-1][i%2]);

			}

		}

		printf("%d\n", dp[len2][len1%2]);

	}

	return 0;

}