数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学JavaScript中的斐波那契数列
斐波那契数列是指这样一个数列：除前两个数外，每个数都是其前两个数之和。该数列以1, 1开始。例如：
1, 1, 2, 3, 5, 8, 13, 21, 34, ….
我们可以编写一个程序来生成第n个数，如下所示：
functionfibNaive(n) {
if (n<= 1) return n;
returnfibNaive(n - 1) + fibNaive(n - 2);
}您可以使用以下方法进行测试：
console.log(fibNaive(7)); console.log(fibNaive(8)); console.log(fibNaive(9)); console.log(fibNaive(4));
这将输出：
13 21 34 3
让我们看看这些函数调用是如何实际发生的：
/** * f(5) * / \ * f(4) f(3) * / \ / \ * f(3) f(2) f(2) f(1) * / \ .......... * f(2) f(1).......... */
当我们调用f(5)时，我们将近4次调用f(2)，并且它会反复运行相同的代码4次。这是一个重叠子问题的情况。尝试对500运行该函数。您将卡住，因为所有这些调用都将花费大量时间。
当我们需要第5个斐波那契数时，我们只需要计算较低的斐波那契数一次，但我们计算它们的次数远多于此。如果我们只将计算出的值存储在某个地方，就可以减少这种冗余计算。这就是动态规划的关键。
计算一次，稍后重复使用。
让我们看看fib函数的记忆实现。
letfibStore = {};
functionfibDP(n) {
if (n<= 1) return n;
if (fibStore[n]) {
returnfibStore[n];
}
fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
returnfibStore[n];
}现在我们使用一个存储区fibStore来跟踪我们已经计算出的值。这减少了过多的冗余计算，并保持了函数的效率。
您可以使用以下方法进行测试：
console.log(fibDP(7)); console.log(fibDP(8)); console.log(fibDP(9)); console.log(fibDP(4));
这将输出：
13 21 34 3
您甚至可以针对巨大的值测试此函数。
更新于：2020年6月22日
407 次浏览
广告