动态规划解决最长公共子序列

#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;

int c[10][10];
int b[10][10];


void LCSLength(int m,int n,char *x,char *y,int c[10][10],int b[10][10]){
	int i,j;
	for(i = 0;i <= m;i++)
		c[i][0] = 0;
	for(i = 0;i <= n;i++)
		c[0][i] = 0;

	for(i = 1;i <= m;i++)
		for(j = 1;j <= n;j++){
			if(x[i] == y[j]){
				c[i][j] = c[i-1][j-1] +1;
				b[i][j] = 1;
			}
			else if(c[i-1][j] >= c[i][j-1]){
				c[i][j] = c[i-1][j];
				b[i][j] = 2;
			}
			else {
				c[i][j] = c[i][j-1];
				b[i][j] = 3;}
		}


}

void LCS(int i,int j,char *x,int b[10][10]){
	if(i == 0|| j == 0)
		return;
	if(b[i][j] == 1){
		LCS(i-1,j-1,x,b);
		printf("%c  ",x[i]);
	}
	else if(b[i][j] == 2)
		LCS(i-1,j,x,b);
	else LCS(i,j-1,x,b);
}

void main(){
	int m,n;
	printf("输入X和Y中的元素数目：");
	scanf("%d %d",&m,&n);

	char *x ;
	x = (char*)malloc((m+1) * sizeof(char));
	char *y;
	y = (char*)malloc((n+1) * sizeof(char));

		printf("输入X中的元素：");
			for(int i = 1;i <= m;i++)
		cin>>x[i];


	printf("输入Y中的元素：");

 	for(i = 1;i <= n;i++)
		cin>>y[i];
	printf("公共子序列为：");
	LCSLength(m,n,x,y,c,b);
	LCS(m,n,x,b);
	printf("\n长度为%d\n",c[m][n]);
	free(x);
	free(y);
}