NYOJ 36 LCS 动态规划入门

尘埃092

于 2013-07-13 15:35:57 发布

阅读量709

点赞数

分类专栏：算法题目

本文链接：https://blog.csdn.net/chenansic/article/details/9318923

版权

算法题目专栏收录该内容

68 篇文章

订阅专栏

本文探讨了字符串匹配问题的解决方法，通过使用动态规划算法实现高效的匹配过程。详细介绍了算法原理、实现步骤及应用实例，展示了算法在实际场景中的高效性能。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include <stdio.h>
#include <string.h>
int max( int a, int b )
{
	return a > b ? a : b;
}
int d[1001][1001];
char s1[2000];
char s2[2000];
int main()
{
	int la, lb, N;
	scanf( "%d", &N );
	while( N-- )
	{
		memset( d, 0, sizeof(d) );
		scanf( "%s", s1 ); la = strlen(s1);
		scanf( "%s", s2 ); lb = strlen(s2);
		for( int i = 1; i <= la; i++ )
			for( int j = 1; j <= lb; j++ )
			{
				if( s1[i-1] == s2[j-1] )
					d[i][j] = d[i-1][j-1] + 1;
				else
					d[i][j] = max( d[i-1][j], d[i][j-1] );
			}
		printf( "%d\n", d[la][lb] );
	}
	return 0; 
}