面试题10：斐波那契数列
递归会存在大量的重复数据。按照如下进行优化
<script>
function Fibonacci(n)
{
if(n===0)
return 0;
if(n===1)
return 1;
let num1=0;
let num2=1;
let fibN;
for(let i=2;i<=n;i++){
fibN=num1+num2;
num1=num2;
num2=fibN;
}
return fibN;
}
</script>
题目二:跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法.
function jumpFloor(number)
{
let F1=1;
let F2=2;
if(number===1)
return 1;
if(number===2)
return 2;
let Fn;
for(let i=3;i<=number;i++){
Fn=F1+F2;
F1=F2;
F2=Fn;
}
return Fn;
}
题目三：变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
假设最后跳1阶 f(n-1)种；最后跳2阶 f(n-2)种；...最后跳n阶 1种
f(n)=f(n-1)+f(n-2)+....+1;
function jumpFloorII(number)
{
// write code here
if(number===1)
return 1;
if(number===2)
return 2;
let f1=1;
let f2=2;
for(let i=3;i<=number;i++){
fn=f1+f2+1;
f1=f1+f2;
f2=fn;
}
return fn;
}
题目四：覆盖矩形
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
function rectCover(number)
{
if(number===0)
return 0;
// write code here
//覆盖一个方框有一种方法
if(number===1)
return 1;
//覆盖两个有2种.横着覆盖，竖着覆盖
if(number===2)
return 2;
let f1=1;
let f2=2;
let fn;
for(let i=3;i<=number;i++){
fn=f1+f2;
f1=f2;
f2=fn;
}
return fn;
}
