当前课程知识点:程序设计基础 > 第六章 递推与动态规划 > 6.4 最长公共子序列问题 > 6.4.2 问题分析
那么这个问题到底该怎么解决呢
那我们可以想一想如果人来去找的话
用眼睛来找的话 我们会怎么找
当然我们很自然就想到说
我肯定先把A和B的第一个字母拿出来比较一下
看他们是不是相等 用我们的代码的语言
计算机的语言来表示呢
表示成说A0和B0是不是相等的
如果他们两个相等 那我们一定很高兴
要找公共的子序列嘛 已经匹配上一个字母了
我们只需要找他们后面的部分
就是对于A来讲下标1开始的那个部分 那个序列
和B下标1开始的那个序列我们继续去比较就可以了
那如果A0和B0不等呢
那至少这个位置他们匹配不上
他们不是一个公共的子序列的部分
那我们就只能说可以想到别的方案
可以想到说 我就试图说挪挪位置
我把A去和B后面的串去比比看
他们的最长公共子序列是什么
那么这两个字母的序列是对称的
所以呢我们也要找一找说
B这个序列去和A从下标1的这个字母开始的
这么一个序列去比 我们也可以找找
这样情况下的最长公共子序列
那最后大不了把这两种情况的所谓的最长公共子序列
再比一次求一个最长的
那这就是我们一个很朴素的
人眼可以根据这个观察去操作的这么一个方法
我们可以用我们的这种数学的语言写更一般化一些
也就是说我其实呢是
去比较在A和B两个序列中的一个对应位置
比如说我比较Ai和Bj对应位置上的这么两个字母
如果他们相等呢我就很高兴
我就说我找到了一个公共的子序列的字母了
然后我只要比较它们剩余的部分了
也就是说我们可以说A从i+1开始的这么一个序列
和B从j+1这两个序列我们去比较就行了
那么如果Ai和Bj不等的话呢
那我们就给错开一个
或者说我们也可以解释成说
那么我们把不等这个位置的字母扔掉呗
如果我把Bj的这个字母扔掉
那我就去比较Ai开始的序列和Bj+1开始的序列
如果我把Ai这个字母扔掉
那我就去比较Ai+1开始的序列和Bj开始的序列
所以我们找到这两个序列求他们的
最长公共子序列就可以了
那我们再从头的看看我们到底应该怎么处理
因为大概有了这想法了
那原始问题呢显然是说我们从A0开始
和B0开始这两个序列进行比较
如果呢A0和B0相等那我可以认为说
两个序列都扔掉这个位置了进行比较
也就是我只要继续比较A1开始的序列和B1开始的序列
那么如果A0和B0不等 那我们扔掉一个
我们接着比较A0开始的序列和B1开始的序列
并且呢我们还要去看看A1开始的序列和B0开始的序列
然后我们再去找所谓的最长的公共子序列
反正在0这个位置上面它们是不可能都有相同字母的
好 对于A0和B0的这两个分支我们继续考察
如果A1和B1这两个字母是相同的
我们又找到了公共子序列的部分
那我们只需要去比较A2开始的序列和B2开始的序列了
如果他们不等呢
两种情况我们需要分别去比较
A1开始序列B2开始序列
和A2开始序列B1开始序列
同样例如说我们就对中间这种情况来看
如果A1和B2他们相等
那么我们就要比较A2开始和B3开始的序列
如果他们不等呢 又是两种情况
那从另一个分支来说呢
我们考虑这个对应位置的字母相等
有一种情况不等 有两种情况
我们现在只画了一部分
如果这个串比较长的话
我们可以想象到说我这个树状结构得画的非常非常复杂
细心的同学已经发现了
虽然我只画了很小的一部分
但是呢这里头明显是有一些重复的
比如说 我们在不同的分支
都需要比较A从1开始的序列和B从1开始的序列
我们在不同的分支都需要比较
A从2开始的序列和B从2开始的序列
我们在不同的分支还要都比较说
A从2开始序列和B从1开始的序列
那么这么多重复的计算
就是因为我们去设计我们这个计算
实际上我们已经学过了这是一个
典型的递归的一个算法的思想
这里头呢是存在着大量的重复计算的
而我们之前也已经学过了说
为了避免这样重复计算呢
我们可以去保存已经算出来的结果
也就是我们保存了A从i开始的串B从j开始的
这两个串的比较结果呢
以后如果还需要计算同样的情形
那我们就可以直接这样取值了
从而避免重复计算
那么这个是我们从人眼观察得到的
一个递推的一个递归的方法
那么今天呢
我们实际上已经介绍了动态规划的这种方法
所以呢我们将会尝试 用动态规划的方法来
重新解决这样一个求最长公共子序列的问题
-1.1 基础知识
-1.2 买菜问题
-1.3 数学运算
-1.4 补充说明
-1.5 总结
--1.5 总结
-程设论道
--程设论道
-师生问答
-第一章 编程初步--语法自测
-2.1 关于超级计算器的几点思考
-2.2 电子秤模拟 — 背景介绍及需求分析
-2.3 电子秤模拟 — 代码实现
-2.4 变量定义与变量类型
-2.5 猜数游戏与数据表示
-2.6 关于变量的讨论
--公告
-2.7 变量体现的计算思维
-程设论道
--程设论道
-师生问答
--师生问答
-第二章 变量与代数思维--语法自测
-3.1 谁做的好事——语义表示
-3.2 谁做的好事——真假检查
-3.3 谁做的好事——循环枚举
-3.4 谁是嫌疑犯——多重循环枚举
-3.5 谁是嫌疑犯——破案线索表示
-3.6 谁是嫌疑犯——用二进制枚举
-程设论道
--程设论道一
--程设论道二
--程设论道三
-师生问答
-第三章 逻辑推理与枚举解题--语法自测
-4.1 插花游戏
-4.2 筛法
-4.3 线性查找
-4.4 折半查找
--4.4.1 提问
-4.5 排序问题
-4.6 总结
--4.6.1 总结
-程设论道
--程设论道二:筛法
-师生问答
-第四章 筛法与查找--语法自测
-5.1 阶乘
-5.2 排序
-5.3 矩阵填充
-5.4 分书与八皇后
-5.5 青蛙过河
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答一
--师生问答二
-第五章 分治思想与递归--语法自测
-6.1 兔子数列问题
-6.2 分鱼问题
-6.3 橱窗的插花问题
-6.4 最长公共子序列问题
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第六章 递推与动态规划--语法自测
-7.1 统计记录总数
-7.2 统计活跃用户数
-7.3 统计在线时长
--7.3.2 结构
-7.4 总结
--7.4.1 总结
-程设论道
--程设论道
-师生问答
--师生问答
-第七章 文本数据处理--语法自测
-8.1 将数据组织成链表
-8.2 提高链表访问效率 —— 哈希链表
-8.3 以二进制文件存储链表
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第八章 非文本数据处理--语法自测
-9.1 自动售卖程序
-9.2 配制水果信息
-9.3 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测