====================
== Hi, I'm Vimiix ==
====================
Practice makes perfect (ง •̀_•́)ง

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

动态规划 algorithms Python

本文是《算法图解》笔记

应用场景

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

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

最长公共子串

场景:

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

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

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

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

求解网格:
注:只列出hish的例子,vista思路相同
hish
f0000
i0100
s0020
h1003
算法描述:
  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

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

求解网络:
fosh
f1111
i1111
s1122
h1123
算法描述:
  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])