用动态规划实现最长公共子序列C语言

思路：
有两个字符数组a，b
分为三种情况：
比较a，b数组当前长度的最后一个字符

1. 相等时， lsc值等于前一段值加1
   即：当a[i-1]==b[j-1]时(因为i,j是从1开始，所以是a[i-1],b[j-1])，lsc[i][j]=lsc[i-1][j-1]+1
2. 不相等，把a数组的最后一个字符去掉的最长公共子序列大于把b数组的最后一个字符去掉的最长公共子序列
   即：当lsc[i-1][j]>=lsc[i][j-1]时，lsc[i][j]=lsc[i-1][j]
3. 不相等，把b数组的最后一个字符去掉的最长公共子序列大于把a数组的最后一个字符去掉的最长公共子序列
   即：当lsc[i-1][j]<lsc[i][j-1]时，lsc[i][j]=lsc[i][j-1]

代码：

#include <stdio.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void LSCLength(char a[],char b[],int c[11][10],int lsc[11][10],int la,int lb)
{
	for(int i=0;i<=la;i++)	lsc[0][i]=0;
	for(int i=0;i<=lb;i++)	lsc[i][0]=0;
	for(int i=1;i<=la;i++)
	{
		for(int j=1;j<=lb;j++){
			if(a[i-1]==b[j-1])
			{
				lsc[i][j]=lsc[i-1][j-1]+1;
				c[i][j]=1;
			}
			else if(lsc[i-1][j]>=lsc[i][j-1])
			{
				lsc[i][j]=lsc[i-1][j];
				c[i][j]=2;
			}
			else{
				lsc[i][j]=lsc[i][j-1];
				c[i][j]=3;
			}
		}
	}

	
}
void LSC(int i,int j,char a[],int c[11][10]) 
{
	if(i==0 || j==0)	return;
	if(c[i][j]==1)
	{
		LSC(i-1,j-1,a,c);
		printf("%3c  ",a[i-1]);
	}
	else if(c[i][j]==2)
	{
		LSC(i-1,j,a,c);
	}
	else
	{
		LSC(i,j-1,a,c);
	}
	
}
int main(int argc, char** argv) {
	char a[10]={'d','i','d','a','c','t','i','c','a','l'};
	char b[9]={'a','d','v','a','n','t','a','g','e'};
	int c[11][10]={0};
	int lsc[11][10]={0};
	LSCLength(a,b,c,lsc,10,9);
	for(int i=0;i<=10;i++)
	{
		for(int j=0;j<=9;j++)
		{
			printf("%d  ",lsc[i][j]);
		}
		printf("\n");
	}
	printf("长度：%d\n比较情况\n",lsc[10][9]);
	
	for(int i = 0;i<11;i++){
		for(int j = 0;j<10;j++){
			printf("%3d",c[i][j]);
		}
		printf("\n");
	}
	LSC(10,9,a,c);
	return 0;
} 

运行结果：