(1)、问题描述：给出2个序列，x是从1到m，y是从1到n，找出x和y的最长公共子序列？
x：A B C B D A B
y：B D C A B A
则：最长公共子序列长度为4，BDAB BCAB BCBA均为LCS(最长公共子序列)；
模型实现图：
(2)、问题解决
代码实现了最长公共子序列的长度
计算
安全
数据库
网络和加速
企业服务
#include<stdio.h>
#define N 10
int LCS(int *a, int count1, int *b, int count2);
int LCS(int *a, int count1, int *b, int count2){
int table[N][N] = {0};
int i;
int j;
for(i = 0; i < count1; i++){
for(j = 0; j < count2; j++){
if(a[i] == b[j]){
table[i+1][j+1] = table[i][j]+1;
}else{
table[i+1][j+1] = table[i+1][j] > table[i][j+1] ? table[i+1][j] : table[i][j+1];
}
}
}
return table[count1][count2];
}
void main(void){
int a[] = {1, 2, 3, 4, 5, 6};
int b[] = {2, 3, 5, 6, 7};
int count1 = sizeof(a)/sizeof(int);
int count2 = sizeof(b)/sizeof(int);
int number;
number = LCS(a, count1, b, count2);
printf("%d\n", number);
}结果截图
(3)、动态规划的特征：
特征一(最优子结构的性质)：一个问题的最优解包含了子问题的最优解；
特征二：重叠子问题，一个递归的过程包含很少的独立子问题被反复计算了多次；
时间复杂度：O(m*n)；
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
