HDOJ_1159：Common Subsequence 解题报告

		a	b	f	c	a	b
	0	0	0	0	0	0	0
b	0	0	1	1	1	1	1
a	0	1	1	1	1	1	2
f	0	1	1	2	2	2	2
c	0	1	1	2	3	3	3
a	0	1	2	2	3	4	4
b	0	1	2	2	3	4	5

本题每个a[i]==b[j]的点都会对以该点位左上角的方阵的全部元素产生+1的效果

理解了这个本质其实直接写个函数使其产生对作用范围内全部元素+1的效果 然后遍历全部input 不过这样的更新量过大 更好的方法就是直接找相邻元素间的递推关系 思维上稍微复杂点 不过程序上就更快了

上述表格里 第一个零元素对应的是f[0][0] 而f[i][j]则表示a的前i个元素和b的前j个元素之间的最长公共子序列的长度 初始条件是f[0][*]和f[*][0]做全为0 实际上是冗余 因为这些数值没有与元素有实际的对应关系 而是而是假设其中一个输入为null时的情况

// HDOJ_1159.cpp : Common Subsequence

#include <iostream>
using namespace std;
char a[1002];
char b[1002];
int f[1002][1002];
int main()
{
	int i, j;
	int alen, blen;
	while ( scanf("%s %s",a+1,b+1)!=EOF ){
		alen = strlen(a+1);
		blen = strlen(b+1);

		for( i=0; i<=alen; i++ )
			for ( j=0; j<alen; j++ )
				f[i][j] = 0;

		for( i=1; i<=alen; i++ )
			for( j=1; j<=blen; j++ ){
				if( a[i]==b[j] )
					f[i][j] = f[i-1][j-1]+1;
				else
					f[i][j] = max(f[i-1][j],f[i][j-1]);
			}
		cout << f[alen][blen] << endl;
		for( i=1; i<=alen; i++ ){
			for( j=1; j<=blen; j++ )
				cout << f[i][j] << " ";
			cout << endl;
		}
	}
	//system("pause");
    return 0;
}

之前用C++输入风格写了个程序 自己这边跑的很好 结果OJ上总RE 后来参照网上其他人的程序才发现 貌似是大数组需要放到main外面声明 不过这样就没法动态分配数组了 至少以我目前的知识不知道如何不浪费内存

如果不是有极长的输入的话 下面的程序也是能用的 另外虽然递推关系没变 不过当时没有让f[0][*]和f[*][0]做全为0的冗余 而是让f的第一行和第一列的元素在相同时为1不同时为0 并作为初始条件 这样导致一部分f[i][j]并不是a的前i+1个元素和b的前j+1个元素之间的最长公共子序列的长度 不过最终的总长度求值是正确的

[picture holder======]

// HDOJ_1159.cpp : Common Subsequence

#include <iostream>
#include <string>
using namespace std;

int main()
{
	int i, j;
	string a,b;
	int alen, blen;
	while ( cin >> a >> b ){	//cin读入string需要<string>头文件
		alen = a.length();
		blen = b.length();
		//cout << alen << " " << blen << endl;	//校验长度是否正确

		int **f = new int*[alen];	//动态分配二维数组
		for( i=0; i<alen; i++ )
			f[i] = new int[blen];
		//memset( f, 0, sizeof(f) );	//memset用在这里会出错 回头找下原因
		for( i=0; i<alen; i++ )
			for( j=0; j<blen; j++ )
				f[i][j] = 0;

		for( i=0; i<alen; i++ )
			if( a[i]==b[0] )	f[i][0] = 1;
		for( j=0; j<blen; j++ )
			if( a[0]==b[j] )	f[0][j] = 1;	//上面两个for初始化第一行和第一列

		for( i=1; i<alen; i++ )
			for( j=1; j<blen; j++ ){
				if( a[i]==b[j] )
					f[i][j] = f[i-1][j-1]+1;
				else
					f[i][j] = max(f[i-1][j],f[i][j-1]);
			}
		cout << f[alen-1][blen-1] << endl;
		for( i=0; i<alen; i++ ){
			for( j=0; j<blen; j++ )
				cout << f[i][j] << " ";
			cout << endl;
		}

	}
	//system("pause");
    return 0;
}