斐波那契数列
本文总结斐波那契数列的一些优化算法及应用。
题目
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
在种子数字 0 和 1 之后，后续的每一个数字都是前面两个数字之和。
解法
- 递归
function fibonacci(n) {
if(n === 0 || n === 1) return n;
return fibonacci(n-1) + fibonacci(n-2);
}
- 递归+缓存
function fibonacci(n) {
let arr= [0, 1];
let result = arr[n];
if(typeof result !== 'number') {
result = fibonacci(n - 1) + fibonacci(n - 2);
arr[n] = result;
}
return result;
}
- 循环
function fibonacci(n) {
let current = 0;
let next = 1;
let temp;
for(let i = 0; i < n; i++) {
temp = current;
current = next;
next += temp;
}
return current;
}
// 解构
function fibonacci(n) {
let current = 0;
let next = 1;
for(let i = 0; i < n; i++) {
[current, next] = [next, current + next];
}
return current;
}
- 尾递归调用
function fib(n, current = 0, next = 1) {
if(n == 0) return 0;
if(n == 1) return next;
return fib(n - 1, next, current + next);
}
应用题
1. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。
提示：f(n) = f(n-1) + f(n-2)
扩展题：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶......也可以跳上n级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。
提示：f(n) = 2n-1
2. 面积问题
如果我们用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问8个2*1的小矩形无重叠地覆盖一个2*8的大矩形，总共有多少种方法？
提示：f(8) = f(7) + f(6)