裴波那切数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
时间限制：3秒 空间限制：32768K
思路
递归实现
代码
function Fibonacci(n)
{
// write code here
function getFibonacci(number) {
if (number > 2) {
return getFibonacci(number - 1) + getFibonacci(number - 2);
} else if (number == 2) {
return 1;
} else if (number == 1) {
return 1;
} else {
return 0;
}
}
return getFibonacci(n);
运行时间：未通过，时间复杂度过高
占用内存：
最佳代码
function Fibonacci(n)
{
// write code here
var arrayFibonacci = [0, 1, 1];
for(let i = 3; i <= n; i++) {
arrayFibonacci[i] = arrayFibonacci[i - 1] + arrayFibonacci[i - 2];
}
return arrayFibonacci[n];
}
运行时间：13ms
占用内存：5436k
满足动态规划的思想，最优子结构、无后效性、子问题重叠；
内存优化，由于每次只使用了前两次计算的结果，因此可以只保存前两次的值：
function Fibonacci(n)
{
// write code here
if (n < 1) {
return 0;
} else {
var pre = 1;
var next = 1;
var i = 3;
while ( i <= n) {
let copyOfNext = next;
next = pre + copyOfNext;
pre = copyOfNext;
i++;
}
}
return next;
}
运行时间：11ms
占用内存：5436k
好像没有变化….
