动态规划法如何来解决最长公共子序列问题_动态规划解决最长公共子序列

最长公共子序列问题。设有两个字符序列X和Y，它们的元素分别存放在数组x[m+1]和y[n+1]中，x[0]和y[0]不放元素。公共子序列存放在数组z[]中。完成如下函数。
2、int CommonOrder(int m,int n,char x[],char y[],char z[])函数功能是返回两字符序列的最长公共子序列长度值。并且公共子序列存放在数组z[]中。
3、写主函数main()，实现输入数组x[]和y[]，调用 CommonOrder函数，并输出公共子序列。
（1）解题思路：引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的 最长公共子序列的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。我是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我根据X[i] = Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。
（2）问题的递归式写成：

（3）算法分析：
由于动态规划法，其中一个for循环的时间性能为O（n * m），是所有循环的最大值，故算法时间复杂度为O(m * n)。
（4）代码如下：

#include<stdio.h>
#include<string.h>
int c[200][200];   //用c[i][j]记录X[i]与Y[j] 的LCS 的长度
int b[200][200];   //b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向
int Max(int m,int n,int i,int j)
{
   
	if(m > n)
	{
   
		b[i][j] = -1;
		return m;
	}
	else
	{
   
		b[i][j] = 1;
		return n;
	}
}
/*递归打印Z的元素内容*/
void print(
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21