目录

引言

例题

核心思路

全部代码

输出样例

引言

公共上升子序列问题是动态规划的经典题目，但是动态规划主要解决的是最长公共上升子序列的长度，要是想逐个输出最长公共上升子序列，就无法使用动态规划了，本文介绍一种用递归思想解决的思路。

例题

一个数的序列（b1,b2,…,bt）,当b1<b2<…<bt时，称这个序列是上升的。对于给定的一个序列，可以得到一些上升的子序列。例如（1,7,3,5,9,4,8），有一些上升子序列，如（1,7），（3,4,8）等。这些子序列中最长的长度是4，如（1,3,5,8）。对于给定的两个序列X=(x1, x2 ,… , xi)和Y=(y1, y2, …, yj) ，输出X和Y的最大公共上升子序列。

核心思路

先分别求出两个数列所有的上升子序列，然后把两者上升子序列的进行比较，求出最长公共上升子序列。其中，比较难以解决的是求出一个数列的所有的子序列，下面给出一种递归解决方法。对于数列a={1，2，3}，在每层递归时，需要选择是否将数列第i个元素添加到这一层递归的数列后面，这就产生了两种分叉情况，添加和不添加（图中分别用√和×表示），同时将两种情况再传入下一层递归，如此反复，直到递归层级等于原数列的数字个数（即图中的第三层递归），然后进行逐层返回并存储每个子序列（存储时再稍加筛选就可以得到所有的上升子序列）。

求出某个数列的所有上升子序列对应的代码如下

void creat(int* a, int size, int* p[], int* creat0, int judge, int next, int* count)
//产生a数列的上升子序列，并返回到* p[]
//*a原数列，size原数列长度，把*a的所有上升子序列返回到指针数组*p[], *creat0每个子序列，judge记录递归层级，next当前上升子序列长度，count返回指针数组*p[]的元素个数
{
	int* creat2 = NULL;int i;
	creat2 = (int*)malloc(size * sizeof(int));//创造一个只属于一个递归过程的数组，用于存放当前子序列
	for (i = 0; i <= next; i++)
	{
		*(creat2 + i) = *(creat0+i);
	}
	if (judge == size)//判断递归是否到了最后一层，如果到了，就进行存储（子序列）
	{

		p[*count] = (int*)malloc((size + 1) * sizeof(int));
		*p[*count] = next;                         //*p[*count](指针指向的第一个元素)存储子序列长度
		if (sift(creat0, next))                   //判断子序列是否是上升的
		{
			for (i = 1; i <= (*p[*count]); i++)    //将上升子序列存入指针数组的一个元素中
			{
				*(p[*count] + i) = *(creat0+i - 1);
			}
			*count = *count + 1;//上升子序列个数+1
		}
		free(creat2);
	}
	else
	{
		creat(a, size, p, creat2, judge + 1, next, count);//进入不添加下一个数的creat递归
		*(creat2 + next) = a[judge];//添加下一个数
		creat(a, size, p, creat2, judge + 1, next + 1, count); //进入添加下一个数的creat递归
	}
}

全部代码

#include
#include
#define SIZE 999
int com(int* a, int* b, int la, int lb);//比较两个数字串是否相等
int maxab(int a, int b);//返回a，b中的最大值
int sift(int *a, int size); //判断子序列是否是上升的
void creat(int *a, int size, int* p[], int *creat0, int judge, int next, int* count);
//产生a数列的上升子序列，并返回到* p[]
//*a原数列，size原数列长度，把*a的所有上升子序列返回到指针数组*p[], *creat0每个子序列，judge记录递归层级，next当前上升子序列长度，count返回指针数组*p[]的元素个数
int main()
{
	int* pa; int* pb; int* fcount;//pa数字串a，pb数字串b，fcount存储a,b的最长上升子序列的序号
	int na, nb,i = 0,j,t, count = 0, max = 0; 
	int* pas[SIZE] = { NULL }; int* pbs[SIZE] = { NULL };//分别存储a，b的上升子序列
	int creat1 = 0 ;//初始递归子序列
	int lpas = 0;//a的上升子序列的个数
	int lpbs = 0;//b的上升子序列的个数
	printf("请输入第一行数字串长度：n");
	scanf("%d", &na);
	pa = (int*)malloc(na * sizeof(int));
	printf("请输入第一行数字串：n");
	while (i < na)
	{
		scanf("%d", pa + i);
		i++;
	}
	creat(pa, na, pas, &creat1, 0, 0, &lpas);//把a的上升子序列返回到指针数组*p[]
	printf("请输入第二行数字串长度：n");
	scanf("%d", &nb);
	pb = (int*)malloc(nb * sizeof(int));
	printf("请输入第二行数字串：n");
	i = 0;
	while (i < nb)
	{
		scanf("%d", pb + i);
		i++;
	}
	creat(pb, nb, pbs, &creat1, 0, 0, &lpbs);//把b的上升子序列返回到指针数组*p[]
	fcount = (int*)malloc(maxab(lpas, lpbs) * sizeof(int));
	count = 0;
	for (i = 1; i < lpas; i++)//遍历a,b的上升子序列
	{
		for (j = 1; j < lpbs; j++)
		{
			if (com(pas[i], pbs[j], *pas[i], *pbs[j]))//找到a,b的公共上升子序列
			{
				if (max < *pas[i])//找到a,b的最长公共上升子序列
				{
					max = *pas[i];
					*fcount = i;
					count = 1;
					continue;
				}
				if (max == *pas[i])//存储a,b的最长公共上升子序列们
				{
					for (t = 0; t < count; t++)
					{
						if (com(pas[i], pas[*(fcount + t)], *pas[i], *pas[*(fcount + t)]))//去除重复的最长上升子序列，如果重复，则不存储
						{
							goto A;
						}
					}
					*(fcount + count) = i;//存储a,b的最长公共上升子序列们
					count++;
				A:;
				}

			}
		}
	}
	if (count == 0) printf("无最长公共上升子序列n");
	else printf("最长公共上升子序列为：n");
	for (i = 0; i < count; i++)
	{
		for (j = 1; j <= max; j++)
		{
			printf("%d ", *(pas[*(fcount + i)] + j));//打印a,b的最长公共上升子序列（们）
		}
		printf("n");

	}
	free(pa);
	free(pb);
	free(pas[lpas]);
	free(pbs[lpbs]);
	free(fcount);
	return 0;
}
int com(int* a, int* b, int la, int lb)//比较两个数列是否相等
{
	if (la > lb)return 0;//先判断长度，一票否决
	if (la < lb)return 0;
	for (int i1 = 1; i1 <= la; i1++)
	{
		if (*(a + i1) > *(b + i1))return 0;
		if (*(a + i1) < *(b + i1))return 0;
	}
	return 1;
}
int maxab(int a, int b)//返回a，b中的最大值
{
	if (a > b)return a;
	else return b;
}
int sift(int *a, int size)    //判断子序列是否是上升的
{
	int i;
	for (i = 0; i < size - 1; i++)
	{
		if (*(a+i) > *(a+i + 1))return 0;
	}
	return 1;
}
void creat(int* a, int size, int* p[], int* creat0, int judge, int next, int* count)
//产生a数列的上升子序列，并返回到* p[]
//*a原数列，size原数列长度，把*a的所有上升子序列返回到指针数组*p[], *creat0每个子序列，judge记录递归层级，next当前上升子序列长度，count返回指针数组*p[]的元素个数
{
	int* creat2 = NULL;int i;
	creat2 = (int*)malloc(size * sizeof(int));//创造一个只属于一个递归过程的数组，用于存放当前子序列
	for (i = 0; i <= next; i++)
	{
		*(creat2 + i) = *(creat0+i);
	}
	if (judge == size)//判断递归是否到了最后一层，如果到了，就进行存储（子序列）
	{

		p[*count] = (int*)malloc((size + 1) * sizeof(int));
		*p[*count] = next;                         //*p[*count](指针指向的第一个元素)存储子序列长度
		if (sift(creat0, next))                   //判断子序列是否是上升的
		{
			for (i = 1; i <= (*p[*count]); i++)    //将上升子序列存入指针数组的一个元素中
			{
				*(p[*count] + i) = *(creat0+i - 1);
			}
			*count = *count + 1;//上升子序列个数+1
		}
		free(creat2);
	}
	else
	{
		creat(a, size, p, creat2, judge + 1, next, count);//进入不添加下一个数的creat递归
		*(creat2 + next) = a[judge];//添加下一个数
		creat(a, size, p, creat2, judge + 1, next + 1, count); //进入添加下一个数的creat递归
	}
}

输出样例