01-F-8 理解LCS & 01-F-9 LCS动态规划1
需积分: 0 190 浏览量
2022-08-03
11:39:51
上传
评论
收藏 1.76MB PDF 举报
01-F-8 理解LCS & 01-F-9 LCS动态规划
#数据结构邓神
Q：为什么算法正确：
1： 单调性： ⽆论如何，每经过⼀次⽐对，原来的问题规模必然减少
具体的，作为输⼊的两个序列，⾄少其⼀的⻓度缩短⼀个单位
最好情况下（也就是只有 0 和 1两种情况） 只需要 O(n+m)的时间 也就是每次两个序列都减少⼀个单位
但问题在于（第⼆个情况） 原问题将会分解为两个问题，更糟糕的是在⼦问题的⼦问题中也会出现这问题，
⽽且可能雷同（这与 Fib 数列的效率低下问题⼀致）
在最坏的情况下 复杂度为 T(n) = O(2^n)
我们会有⼤量的重复实例的计算，我们是否也可以采⽤记忆法？
最坏的情况下先后攻共计出现 O(2^n) 个
但是各个⼦问题分别对应于 A 与 B 某个前缀的总和
因此总共不超过 n*m 种
采⽤ 动态规划的⽅法，只需要 O(n*m) 时间就可以计算出所有问题
评论0