JavaScript高级算法之动态规划实例分析

但要注意的是递归写起来简洁，但实际上执行的效率并不高。

我们再看看动态规划的算法：

动态规划解决方案从底部开始解决问题， 将所有小问题解决掉， 然后合并成一个整体解决方案， 从而解决掉整个大问题 。

实例举例 （计算斐波那契数列）

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........

这个数列从第3项开始，每一项都等于前两项之和。

针对这个数列，可以用一个递归的函数去计算第n项 数值

确实是个非常简洁的代码，上面有被注释的代码 ，是用来打印出当n=多少，要执行多少次函数，不过明眼人一眼就能看出来执行的次数随着n的变大，次数也会非常恐怖增长。

当n=5的时候，递归树已经长的很大了……可以预见当n=10，甚至n=100的时候……

明白了递归函数执行效率之差，我们再来看的动态规划是如何做的

通过数组 val 中保存了中间结果， 如果要计算的斐波那契数是 1 或者 2， 那么 if 语句会返回 1。 否则，数值 1 和 2 将被保存在 val 数组中 1 和 2 的位置。

循环将会从 3 到输入的参数之间进行遍历， 将数组的每个元素赋值为前两个元素之和， 循环结束， 数组的最后一个元素值即为最终计算得到的斐波那契数值， 这个数值也将作为函数的返回值。

接下来可以写个简单的测试函数，来对比两者的运行时间。

打印函数执行

结果如下：

最后， 你或许已经意识到在使用迭代的方案计算斐波那契数列时， 是可以不使用数组的。

需要用到数组的原因是因为动态规划算法通常需要将中间结果保存起来。

以下是迭代版本的斐波那契函数义

当然这个迭代版本的与数组的版本的效率也是相同的。

相关推荐：

php算法学习之动态规划

php算法学习之之动态规划（二）

动态规划之找零问题详解

以上就是JavaScript高级算法之动态规划实例分析的详细内容，更多请关注Gxl网其它相关文章！