动态规划(Dynamic programming)— JavaScript 描述

《数据结构与算法 JavaScript 描述》这本书错误好多,为什么译者不把这些错误纠正呢?

在工作中,我们都用过递归,用俗话说就是函数自己调用自己;而动态规划一般被认为是和递归相反的一种解决问题的思路:递归是从解决一个大问题开始,通过逐步解决一些小问题,来使最终的问题得到解决;动态规划的思路则恰恰相反。

我们直接来看一些例子,大家有时间可以仔细揣摩,代码有不妥的地方,多交流。

斐波拉契数列

我们先看使用递归的方式。

再看使用动态规划的思路。

递归的代码十分简洁,但是效率很低,因为每一次都要重复进行计算,除非把一些中间结果保存下来;动态规划的代码效率很高,通过数组把一些中间值保存下来了。

顺带再看看使用循环的思路。

获取最长公共子串

比如说,两个字符串 “addcc” 和 “bddcc”,他们之间最长的相似字符是“ddcc”,怎么实现这个解法呢?

先看暴力破解的方式。

再看使用动态规划的例子。

啊,代码有点多,我又懒于讲解,还是仔细看代码吧。总之,使用递归可以解决的问题,也可以使用动态规划的思路去解决,而且效率更高,但是需要保持临时的计算结果。

下面是所有的代码,包含了经典的背包问题。

参考链接

https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92

数据结构与算法JavaScript描述

曾小乱

作者: 曾小乱

喜欢写点有意思的东西

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.