前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >深入理解动态规划算法 - 最长公共子序列

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

作者头像
算法与编程之美
发布2019-07-17 17:40:02
5480
发布2019-07-17 17:40:02
举报
文章被收录于专栏:算法与编程之美

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

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

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

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

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

前面三篇文章已经为大家介绍了利用动态规划算法解决问题的思路以及相关的代码实现,最为核心的就是第一步利用数学中函数的思想来建立模型,然后求解问题。这三个问题构建的数学函数都有一个共同的特征就是所构建的函数都是一元函数即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 团队


微信号:算法与编程之美

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-05-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法与编程之美 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
全站加速网络
全站加速网络(Enterprise Content Delivery Network,以下简称 ECDN)为您提供稳定高效的网络加速服务,适用于动静混合、纯动态、跨国、上传等多种加速场景。ECDN 网络资源丰富,同时融合静态缓存、智能路由、协议优化、多路传输、抗抖动等自研技术,加速效果更加显著;接入便捷,功能配置灵活多样,可满足您个性化的业务需求。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档