深入理解动态规划算法 | 最长公共子序列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)。是否可以从上述个例推出一般的结论呢?预知后事如何,欢迎持续关注公众号系列文章。


结语

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


目录
相关文章
|
2月前
|
存储 算法
深入了解动态规划算法
深入了解动态规划算法
75 1
|
2月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
1月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
53 2
|
2月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
104 2
动态规划算法学习三:0-1背包问题
|
2月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
80 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
2月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
175 0
动态规划算法学习二:最长公共子序列
|
2月前
|
存储 人工智能 算法
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
|
2月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
166 0
|
2月前
|
算法 C++
【算法解题思想】动态规划+深度优先搜索(C/C++)
【算法解题思想】动态规划+深度优先搜索(C/C++)
|
4月前
|
机器学习/深度学习 算法 Java
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法