深入理解动态规划算法 - 最长公共子序列

通过欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

深入理解动态规划算法 - 凑硬币

深入理解动态规划算法 - 爬楼梯

深入理解动态规划算法 - 凑整数

前面三篇文章已经为大家介绍了利用动态规划算法解决问题的思路以及相关的代码实现，最为核心的就是第一步利用数学中函数的思想来建立模型，然后求解问题。这三个问题构建的数学函数都有一个共同的特征就是所构建的函数都是一元函数即y = f(x)。

如凑硬币的问题“面值为1元、3元、5元的硬币若干，如何用最少的硬币凑够11元？”。

所构建的函数为y=f(x)，表示凑够x元需要用最少的硬币是y，从而所求的问题就可以转化为求f(11)。

这个函数是一元函数，自变量x的取值为自然数1,2,3,...

那么什么情况下需要构建二元函数来求解动态规划问题呢？本文将为大家介绍一个二元函数的求解问题。

问题描述

最长公共子序列Longest Common Subsequence即(LCS)问题指的是求解两个序列的最长公共子序列及其长度。

假设有以下两个序列，分别为：

s1 = AFDAAFDSA

s2 = FDAFD

则s1和s2的最长公共子序列为’FDAFD’，长度为5。

这里面需要注意的是最长公共子序列并不要求序列必须是连续的，如DFAFD在序列a中并不是连续的。

问题分析

如何对上面的LCS问题进行建模求解？

之前介绍的三个问题都可以直接建模y=f(x)就可以很快解决问题，但是本题有所区别。本题指定了两个输入，即序列s1和序列s2，而之前的题目都只有一个输入。两个输入即意味着有两个自变量，不妨设为x1和x2。

使用x1表示序列s1的长度，自变量x1的取值为: 9,8,...,1,0

使用x2表示序列s2的长度，自变量x2的取值为: 5,4,3,2,1,0

构建函数f(x1,x2)则表示序列s1长度为x1，序列s2长度为x2的最长公共子序列的长度。有了上述二元函数的定义后，本题就可以转化为求解f(9,5)=?

解决方案

如何求解f(9,5)?

首先还是需要明白这个函数表示的含义，第一个序列的长度为9即'AFDAAFDSA'，第二个序列的长度为5即'FDAFD'。f(9,5)表示的就是这样的两个序列的最长公共子序列的长度。

通过之前三篇博客求解一元函数的经验告诉我们，在构建函数之后，就需要考查递推关系。由于本文是二元函数，因此需要考查f(9,5)与f(8,4)、f(9,4)、f(8,5)三个函数的递推关系。

1、f(9,5)与f(8,4)的关系

f(9,5)表示的是求以下两个序列的最长公共子序列的长度。

s1 = AFDAAFDSA

s2 = FDAFD

f(8,4)表示的是求以下两个序列的最长公共子序列的长度。

s1 = AFDAAFDS

s2 = FDAF

从直观上可以看到：

f(9,5) = 5

f(8,4) = 4

2、f(9,5)与f(9,4)的关系

f(9,5)表示的是求以下两个序列的最长公共子序列的长度。

s1 = AFDAAFDSA

s2 = FDAFD

f(9,4)表示的是求以下两个序列的最长公共子序列的长度。

s1 = AFDAAFDSA

s2 = FDAF

从直观上可以看到：

f(9,5) = 5

f(9,4) = 4

3、f(9,5)与f(8,5)的关系

f(9,5)表示的是求以下两个序列的最长公共子序列的长度。

s1 = AFDAAFDSA

s2 = FDAFD

f(8,5)表示的是求以下两个序列的最长公共子序列的长度。

s1 = AFDAAFDSA

s2 = FDAFD

从直观上可以看到：

f(9,5) = 5

f(8,5) = 5

从上述1、2、3点的分析，可以得出f(9,5) = f(8,5)。是否可以从上述个例推出一般的结论呢？

预知后事如何，且听下回分解。

END

主 编 | 张祯悦

where2go 团队

微信号：算法与编程之美

温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！