专栏首页算法channel「动态规划后篇」:考量适用指标

「动态规划后篇」:考量适用指标

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。

01

你会学到什么?

前三天的推送都是关于动态规划算法的,先通过一个《装水最多的容器》初步感受了动态规划是怎么一回事,相比于直观的枚举算法,它能使求解更快地收敛;之后,推送了求解有效括号对的最大数,在求解过程中,根据两种情况分别建立了递推公式;接着解决了动态规划常常需要一个O(n)或更大的空间以及这样做得到个回报,即效率上的提升,并通过一个典型的爬楼梯的实际例子进一步验证了空间确实能够换取时间。

经过以上三天对动态规划的初步研究后,今天我们将要解决的问题只有一个,也是最为核心的问题,那就是什么样的问题适合用动态规划?

我想这也是大家一定想知道的。

02

核心问题

动态规划是好,但是我怎么就能知道我这个问题就能用动态规划来求解呢?

我们还得从面对的这个实际问题具有的特征入手吧,如果它符合动态规划的主要条件,那么就可以尝试用动态规划。

一般地,动态规划需要求解的问题具有2个核心特征:

  1. optimal-substructure property,最优化的子结构属性
  2. overlapping subproblems,重叠的子问题集

下面,解释什么是最优化的子结构属性。如果一个问题的最优解包含在一系列的子问题集的最优解,那么它就称为具有最优化的子结构属性。

还是拿爬楼梯的例子,如果想求解爬到第 i 层楼梯的所有方法,不就是相当于以下这个子问题 (subproblem) 吗:

求爬到第 i-1层的所有方法,和爬到第 i-2层的所有方法,两者的累计和,然后爬到第 i-1层的所有方法。

那么爬到第 i-1 层的所有方法,不又是一个子问题吗,相对于爬到第 i 层的方法不就叫 subsubproblem 吗!

这个爬楼梯问题是非常明显地具有最优化的子结构属性。

再来看下重叠的子问题是怎么定义的,下面是算法导论上解释

When a recursive algorithm revisits the same problem repeatedly, we say that the optimization problem has overlapping subproblems.

意思是说,当一个递归算法再次访问同一个问题时,这种事会出现一遍又一遍的,我们说这个最优化问题有重叠的子问题集。

这个有点抽象,我试着解释下,还是爬楼梯,如果我们分别求出了爬到第 i-1、第 i-2 层的所有方法,那么在求解爬到第 i 层的所有方法时,我们还得去解决爬到第 i-1、第 i-2 层的所有方法,这就是重叠的子问题。

当然,动态规划算法此时不会如此的傻,它会开辟一段内存,记录下爬到第 i-1、第 i-2 层的所有方法,然后在用到的时候直接 look up 了,这也是昨天提到的用空间换取时间的方法。

好了,以上便是两个动态规划问题常常具备的特征,一般地,我们待解决的问题满足了这两个特征,就值得试一试动态规划。

下面再看一个应用动态规划求解longest common subsequence (LCS) 的例子。

03

LCS

LCS的概念

给定两个字符串 x 和 y, 它们的最长子序列具有的长度。 这个概念容易让人误解,以为最长的子字符串必须是相邻的。其实是不必的! 例如 X = "ABCBDAB" , Y = "BDCABA",则 最长子序列长度为4,为 B C A B

例子分析

为什么可以用动态规划来求解? 看看满足那两个特征吗。第一,是最优化的子问题吗? 是!

以下分析是LCS最重要的部分

如果字符串 Xm 和 字符串 Yn 的 X.charAt(m) 和 Y.charAt(n) 相等,那么最长子字符串一定等于字符串 Xm-1 和 字符串 Yn-1 的最长子字符串再加上这个相等字符。

如果字符串 Xm 和 字符串 Yn 的X.charAt(m) 和 Y.charAt(n)不相等,那么最长子字符串一定等于以下两者的较大者:

  1. 字符串 Xm-1 和 字符串 Yn 的最长子字符串。
  2. 字符串 Xm 和 字符串 Yn-1 的最长子字符串。

根据上面的分析,子问题具有最优化的子结构属性,并且容易看出也具备重叠的子问题集,因为求Xm和Yn的最长子字符串要用到Xm-1或 Yn-1的中的至少一个。

上面的分析,实际上得出了一个递推公式,具体的体现在下面的代码中。

04

LCS 代码实现

//返回x和y的最长子串 public static int lcs(String x, String y){ return lcf(x,y,x.length()-1,y.length()-1); } //i : x索引 private static int lcs(String x, String y, int i, int j){ //递归返回的条件 if(i==-1 || j==-1) return 0; //如果相等 if(x.charAt(i)==y.charAt(j)){ return lcf(x,y,i-1,j-1)+1; } //如果不等,返回较大者 return Math.max(lcf(x,y,i-1,j), lcf(x,y,i,j-1)); }

算法的时间复杂度为 O(x.length()+y.length()),空间复杂度为函数的入栈空间。

05

总结

回答了适合动态规划求解的问题主要考量的2个指标,满足了这两个指标后,便能找出递推公式,最后不要忘了递归返回的条件。

本文分享自微信公众号 - 算法channel(alg-channel),作者:alg-flody

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-11-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2500字 字符串专题总结

    除了常见的数值型,字符串是另一种常遇到的类型。一般使用一对单引号或一对双引号表示一个字符串。

    double
  • 动态规划中篇:爬楼梯

    主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

    double
  • BAT面试题27:读6行Python代码,计算关于列表操作的值

    double
  • Golang语言社区--【基础知识】常量

    常量是指该程序可能无法在其执行期间改变的固定值。这些固定值也被称为文字。 常量可以是任何像一个整型常量,一个浮点常量,字符常量或字符串文字的基本数据类型。还有枚...

    李海彬
  • Golang语言社区--【基础知识】常量

    常量是指该程序可能无法在其执行期间改变的固定值。这些固定值也被称为文字。 常量可以是任何像一个整型常量,一个浮点常量,字符常量或字符串文字的基本数据类型。还有枚...

    李海彬
  • Golang语言社区--【基础知识】常量

    常量是指该程序可能无法在其执行期间改变的固定值。这些固定值也被称为文字。 常量可以是任何像一个整型常量,一个浮点常量,字符常量或字符串文字的基本数据类型。还有枚...

    李海彬
  • 用单纯形法求解线性规划(linear programming)问题,速度到底有多快呢?

    我们最早接触到的与运筹学相关的知识可能就是线性规划问题了。求解线性规划问题的基本方法是单纯形法(Simplex algorithm),与单纯形法相关的方法我们...

    用户1621951
  • 你必须知道的11个微前端框架

    微前端将前端整体分解为许多更小、更易管理的片段。每个团队可以端到端地拥有自己的功能,可以在自己的代码库中工作,可以独立发布版本,可以不断进行小的增量升级,还可以...

    深度学习与Python
  • 《JavaScript程序设计》第2课:JS类型系统

    JS类型系统可以分为标准类型和对象类型,进一步标准类型又可以分为原始类型和引用类型,而对象类型又可以分为内置对象类型、普通对象类型、自定义对象类型。 ? 1. ...

    陈树义
  • js笔记

    1.克隆对象 克隆数组: var country=['中国','美国']; var copyCountry=country.slice(0); 克隆对象: va...

    用户1055830

扫码关注云+社区

领取腾讯云代金券