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

本文主要是介绍深入理解动态规划算法 | 最长公共子序列LCS，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

所构建的函数为y=f(x)，表示凑够x元需要用最少的硬币是y，从而所求的问题就可以转化为求f(11)。这个函数是一元函数，自变量x的取值为自然数1,2,3,...

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

1. 问题描述

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

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

s1 = AFDAAFDSA

s2 = FDAFD

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

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

2. 问题分析

如何对上面的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)=?

3. 解决方案

如何求解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)。是否可以从上述个例推出一般的结论呢？预知后事如何，欢迎持续关注公众号系列文章。

结语

前面都是通过一元函数对问题进行建模，本文的问题稍微复杂，需要利用二元函数进行建模求解。当模型建立完成后，就可以用数学的语言对问题进行描述和求解，同时也简化了问题。后面将持续更新介绍二元函数的求解和更多动态规划求解问题。

 where2go 团队

这篇关于深入理解动态规划算法 | 最长公共子序列LCS的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！