Algorithm_最长公共子序列

发表于 | 分类于 | 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// LongestPublicChildSequence.cpp : 定义控制台应用程序的入口点。

#include "stdafx.h"
/**
最长公共子序列，子序列指元素间顺序不变，但不要求连续的数组元素集合
最长公共子序列，指两个数组共有的子序列中最长的那个一个
分类：动态规划
作者：夏军
时间：2018年5月7日
**/
int getMax(int a,int b) {
	return a>b?a:b;
}

int main()
{
	char x[8] = {'A','B','C','B','A','C','B','A'};
	char y[6] = {'B','D','C','A','B','A'};
	int child[9][7];
	//数组初始化
	for(int i = 0;i < 9;i++) {
		for(int j = 0;j < 7;j++) {
			child[i][j] = 0;
		}
	}
	
	for(int i = 1;i < 9;i++) {
		for(int j = 1;j < 7;j++) {
			if(x[i] == y[j]) {//末尾相同，公共子序列长度加1
				child[i][j] = child[i-1][j-1]+1;
			} else {
				child[i][j] = getMax(child[i-1][j],child[i][j-1]);
			}
		}
	}

	printf("最长公共子序列的长度是：%d",child[8][6]);
	return 0;
}