402.cc永利-计算机解决问题没有奇技淫巧,但动态规划还是有点套路

2020-01-11 12:33:24   【浏览】3055

402.cc永利-计算机解决问题没有奇技淫巧,但动态规划还是有点套路

402.cc永利,作者 | labuladong

来源 | labuladong(id:labuladong)

【导读】动态规划算法似乎是一种很高深莫测的算法,你会在一些面试或算法书籍的高级技巧部分看到相关内容,什么状态转移方程,重叠子问题,最优子结构等高大上的词汇也可能让你望而却步。

而且,当你去看用动态规划解决某个问题的代码时,你会觉得这样解决问题竟然如此巧妙,但却难以理解,你可能惊讶于人家是怎么想到这种解法的。

实际上,动态规划是一种常见的「算法设计技巧」,并没有什么高深莫测,至于各种高大上的术语,那是吓唬别人用的,只要你亲自体验几把,这些名词的含义其实显而易见,再简单不过了。

至于为什么最终的解法看起来如此精妙,是因为动态规划遵循一套固定的流程:递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法。这个过程是层层递进的解决问题的过程,你如果没有前面的铺垫,直接看最终的非递归动态规划解法,当然会觉得牛逼而不可及了。

当然,见的多了,思考多了,是可以一步写出非递归的动态规划解法的。任何技巧都需要练习,我们先遵循这个流程走,算法设计也就这些套路,除此之外,真的没啥高深的。

以下,先通过两个个比较简单的例子:斐波那契和凑零钱问题,揭开动态规划的神秘面纱,描述上述三个流程。后续还会写几篇文章探讨如何使用动态规划技巧解决比较复杂的经典问题。

首先,第一个快被举烂了的例子,斐波那契数列。请读者不要嫌弃这个例子简单,因为简单的例子才能让你把精力充分集中在算法背后的通用思想和技巧上,而不会被那些隐晦的细节问题搞的莫名其妙。后续,困难的例子有的是。

步骤一、暴力的递归算法

int fib(int n) { if (n == 1 || n == 2) return 1; return fib(n - 1) + fib(n - 2);}

这个不用多说了,学校老师讲递归的时候似乎都是拿这个举例。我们也知道这样写代码虽然简洁易懂,但是十分低效,低效在哪里?假设 n = 20,请画出递归树。

ps:但凡遇到需要递归的问题,最好都画出递归树,这对你分析算法的复杂度,寻找算法低效的原因都有巨大帮助。

这个递归树怎么理解?就是说想要计算原问题 f(20),我就得先计算出子问题 f(19) 和 f(18),然后要计算 f(19),我就要先算出子问题 f(18) 和 f(17),以此类推。最后遇到 f(1) 或者 f(2) 的时候,结果已知,就能直接返回结果,递归树不再向下生长了。

递归算法的时间复杂度怎么计算?子问题个数乘以解决一个子问题需要的时间。

子问题个数,即递归树中节点的总数。显然二叉树节点总数为指数级别,所以子问题个数为 o(2^n)。

解决一个子问题的时间,在本算法中,没有循环,只有 f(n - 1) + f(n - 2) 一个加法操作,时间为 o(1)。

所以,这个算法的时间复杂度为 o(2^n),指数级别,爆炸。

观察递归树,很明显发现了算法低效的原因:存在大量重复计算,比如 f(18) 被计算了两次,而且你可以看到,以 f(18) 为根的这个递归树体量巨大,多算一遍,会耗费巨大的时间。更何况,还不止 f(18) 这一个节点被重复计算,所以这个算法及其低效。

这就是动态规划问题的第一个性质:重叠子问题。下面,我们想办法解决这个问题。

步骤二、带备忘录的递归解法

明确了问题,其实就已经把问题解决了一半。即然耗时的原因是重复计算,那么我们可以造一个「备忘录」,每次算出某个子问题的答案后别急着返回,先记到「备忘录」里再返回;每次遇到一个子问题先去「备忘录」里查一查,如果发现之前已经解决过这个问题了,直接把答案拿出来用,不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」,当然你也可以使用哈希表(字典),思想都是一样的。

int fib(int n) { if (n < 1) return 0; // 备忘录全初始化为 0 vector memo(n + 1, 0); // 初始化最简情况 memo[1] = memo[2] = 1; return helper(memo, n);}int helper(vector& memo, int n) { // 未被计算过 if (n > 0 && memo[n] == 0) memo[n] = helper(memo, n - 1) + helper(memo, n - 2); return memo[n];}

现在,画出递归树,你就知道「备忘录」到底做了什么。

实际上,带「备忘录」的递归算法,把一棵存在巨量冗余的递归树通过「剪枝」,改造成了一幅不存在冗余的递归图,极大减少了子问题(即递归图中节点)的个数。

递归算法的时间复杂度怎么算?子问题个数乘以解决一个子问题需要的时间。

子问题个数,即图中节点的总数,由于本算法不存在冗余计算,子问题就是 f(1), f(2), f(3) ... f(20),数量和输入规模 n = 20 成正比,所以子问题个数为 o(n)。

解决一个子问题的时间,同上,没有什么循环,时间为 o(1)。

所以,本算法的时间复杂度是 o(n)。比起暴力算法,是降维打击。

至此,带备忘录的递归解法的效率已经和动态规划一样了。实际上,这种解法和动态规划的思想已经差不多了,只不过这种方法叫做「自顶向下」,动态规划叫做「自底向上」。

啥叫「自顶向下」?注意我们刚才画的递归树(或者说图),是从上向下延伸,都是从一个规模较大的原问题比如说 f(20),向下逐渐分解规模,直到 f(1) 和 f(2) 触底,然后逐层返回答案,这就叫「自顶向下」。

啥叫「自底向上」?反过来,我们直接从最底下,最简单,问题规模最小的 f(1) 和 f(2) 开始往上推,直到推到我们想要的答案 f(20),这就是动态规划的思路,这也是为什么动态规划一般都脱离了递归,而是由循环迭代完成计算。

步骤三、动态规划

有了上一步「备忘录」的启发,我们可以把这个「备忘录」独立出来成为一张表,就叫做 dp table 吧,在这张表上完成「自底向上」的推算岂不美哉!

上一篇:心理测试:烧脑推理之神秘的线索,测出你的思维发散能力如何!
下一篇:龙虎榜机构新动向:净买入5股 净卖出7股

相关新闻