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

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

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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-53-Maximum Subarray(动态规划详解)

22240
来自专栏数据结构与算法

P1488 肥猫的游戏

题目描述 野猫与胖子,合起来简称肥猫,是一个班的同学,他们也都是数学高手,所以经常在一起讨论数学问题也就不足为奇了。一次,野猫遇到了一道有趣的几何游戏题目,便拿...

43570
来自专栏ACM算法日常

LIS的简单应用:UVA-437

上一次紫芝详细地介绍了动态规划中的经典问题LIS,今天我们抽出一个类似思想的简单题目进行实践练习。

10630
来自专栏数据结构与算法

一种递推组合数前缀和的Trick

\(S(n, m)\)可以看做是杨辉三角上的一行,而\(S(n+1, m)\)是他的下一行

23830
来自专栏开发技术

排序之快速排序(下)

快排上是可以进行优化的,那么可以进行哪些优化了,是不是和你想的一样了? 我们往下看

13720
来自专栏牛客网

深信服面试 C++/云计算面经

27450
来自专栏wym

分治算法概念

  分治算法的设计思想是,将一个难以直接诶解决的大问题,分割成一些规模较小的相同的问题,以便各个击破,分而治之。

17020
来自专栏专知

【专知-关关的刷题日记18】Leetcode 35. Search Insert Position

题目 Given a sorted array and a target value, return the index if the target is fo...

38290
来自专栏云时之间

NLP入门之形式语言与自动机学习(一)

任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们很流行的框架和工具很有可能几年内就会变成过时的东西.但是计算机...

49060
来自专栏算法channel

除自身累乘算法题,又有创意解法了

一个数组,求除了某元素自身位置之外的其他元素累积相乘,返回一个同长度的数组。有两个要求比较苛刻: 1) 不能用除法 2) 时间复杂度O(n),空间复杂度O(1)...

14000

扫码关注云+社区

领取腾讯云代金券