扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
(1)、问题描述：给出2个序列，x是从1到m，y是从1到n，找出x和y的最长公共子序列？
成都创新互联公司主营延川网站建设的网络公司,主营网站建设方案,成都App定制开发,延川h5小程序制作搭建,延川网站营销推广欢迎延川等地区企业咨询
x：A B C B D A B
y：B D C A B A
则：最长公共子序列长度为4，BDAB BCAB BCBA均为LCS(最长公共子序列)；
模型实现图：
(2)、问题解决
代码实现了最长公共子序列的长度
#include#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)；
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网