[算法笔记]动态规划之最长公共子串和最长公共子序列

本文是《算法图解》笔记

应用场景

一切脱离实际应用场景的算法都是耍流氓！

• 生物学家根据最长公共序列来确定 DNA 链的相似性，进而判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。
• 源代码管理中，git diff指令，可以查找出编辑前后文件的差异，这是基于动态规划实现的。
• 编辑距离（levenshtein distance），判断字符串的相似程度，也是基于动态规划计算。可以通过这个技术从拼写检查到判断用户上传的资料是否是盗版。（这样看来，我猜想大学论文查重应该也是基于动态规划算法:P）
• Microsoft Word等软件中具有断字功能，使用动态规划可以确定什么地方断字以确保行长一致。

最长公共子串

场景：

某个用户在网站搜索框中输入一个字符串 hish，但其实用户想输入的是 fish

介绍这个网站的可选字典里面只有 fish 和 vista 这两个相似单词

猜测用户到底想要搜索的是什么字符串？

在动态规划中，目标是要将某个指标最大化，在这个例子中，要找出两个单词的公共子串。更大的那个即为结果。

求解网格：

注：只列出hish的例子，vista思路相同

	h	i	s	h
f	0	0	0	0
i	0	1	0	0
s	0	0	2	0
h	1	0	0	3

算法描述：

1. 如果两个字母不同，值为0
2. 如果两个字母相同，值为左上角邻居的值加一

伪代码：

if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = 0

最长公共子序列

场景

假设用户不小心输入了 fosh ，要判断他原本要输入的是 fish 还是 fort

这时候需要使用最长公共子序列来比较

求解网络：

	f	o	s	h
f	1	1	1	1
i	1	1	1	1
s	1	1	2	2
h	1	1	2	3

算法描述:

1. 如果两个字母不同，就选择上方和左方邻居格子中较大的那个值
2. 如果两个字母相同，值为左上方格子中的值加一

伪代码：

if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = max(cell[i-1][j], cell[i][j-1])

博客地址： http://vimiix.com