实现斐波那契数列:
- fib(1) = 1
- fib(2) = 1
- fib(n) = fib(n-1) + fib(n-2)
递归实现
function fib(n) {
if(n === 1 || n === 2) return 1
return fib(n-1) + fib(n-2)
}
非递归实现
function fn(n) {
let last1 = 1, last2 = 1, temp
for(let i = 3; i <= n; i++) {
temp = last1 + last2
last1 = last2
last2 = temp
}
return last2
}
用空间换效率
function fib(n) {
let arr = [0, 1, 1]
let(i=3; i<=n; i++) {
arr[i] = arr[i-1] + arr[i-2]
}
return arr[n]
}
使用缓存提升效率
function fib(n) {
let cache = [0, 1, 1]
function _fib(n) {
if(cache[n]) return cache[n]
cache[n] = _fib(n-1) + _fib(n-2)
return cache[n]
}
return _fib(n)
}
