有一类算法问题类似斐波那契数列，而且解决办法基本差不多。

不了解斐波那契套路的可以看

跳台阶问题

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析设到第n阶总共有f(n)种跳法，而且想跳到第n阶只有两种可能，要么从第n-1阶跳一阶到达，要么从第n-2阶跳两阶到达，所以递推式为f(n)=f(n-1)+f(n-2)。特殊情况为，n=0的时候跳法为0；n=1时，跳法为1；n=2时，跳法为2递归

function jump(n) {    if(n < 1)        return 0;    if(n === 1)        return 1;    if(n === 2)        return 2;    return jump(n-1) + jump(n-2);}

非递归

function jumpFloor(number){    if(number < 1)           return 0;    if(number === 1)        return 1;    if(number === 2)        return 2;    var s1 = 1;    var s2 = 2;    var res =  0;    for(var i = 3;i <= number;i++){        res = s1 + s2;        s1 = s2;        s2 = res;    }    return res;}

变态跳台阶问题

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析变态的跳台阶问题处理起来确实是有些棘手，一次可以跳上的阶数是不定的。先看n=0时，跳法f(0)=0；n=1，只能是从第0个台阶跳过来，跳法f(1)=1;n=2，可能是第0个台阶跳了2阶或者从第1个台阶跳了1阶，跳法f(2)=f(0)+f(1);n=3，可能是第0个台阶跳了3阶、第1个台阶跳了2阶、第2个台阶跳了1阶，跳法f(3)=f(0)+f(1)+f(2);...n=n-1，跳法f(n-1)=f(0)+f(1)+f(2)+...+f(n-2);n=n，跳法f(n)=f(0)+f(1)+f(2)+...+f(n-1);由上面两个等式得：f(n) = f(n-1)+f(n-1) = 2f(n-1)代码实现：

function jumpFloorII(number){    if(number < 1)        return 0;    if(number === 1)        return  1;    return 2*jumpFloorII(number-1)}

矩阵覆盖

题目描述

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？分析ps：为了方便分析问题，给每个小矩形不同的颜色，其实他们之间没有差别假设上图为用n个21的小矩形无重叠地覆盖一个2n的大矩形，方法数为f(n)，那么f(n)可以从哪些情况推导出来呢？首先很明显我们知道，2*1的小矩形要么是横着放要么是竖着放，所以f(n)的情况只能由以下两种情况得来：这种情况只需要再加一个竖着的小矩形就可以了，所以这种情况其实是f(n-1)这种情况下，只需要再加一个横着的小矩形就可以了，但是由于这种横着的小矩形只能成对出现，所以这种情况其实是f(n-2)综上，f(n) = f(n-1)+f(n-2)特殊情况时，f(0)=0，f(1)=1，f(2)=2代码实现递归版

function rectCover(n){    if(n === 0)        return 0;    if(n === 1)        return 1;    if(n === 2)        return 2;    return rectCover(n-1) + rectCover(n-2)}

非递归版

function rectCover(n){    if(n === 0)        return 0;    if(n === 1)        return 1;    if(n === 2)        return 2;    var s1 = 1, s2 = 2;    var res = 0;    for(var i = 3;i <= n;i++) {        res = s1 + s2;        s1 = s2;        s2 = res;    }        return res;}

母牛生小牛问题

题目描述

假设农场中成熟的母牛每年只会生一头小母牛，且永远不会死。第一年农场有1头成熟的母牛，从第二年开始，母牛开始生小母牛，每只小母牛3年之后成熟又可以生小母牛。给定整数N，求N年后牛的数量。分析设f(n)为n年后牛的数量，则第n年牛的来源有两个。首先，牛是永远不会死的，所以第n-1的牛都会活到第n年；其次，还有一部分新生的牛，因为每只小母牛3年之后成熟才可以生小母牛，所以第n-3年的未成熟小母牛到了第n年会成熟且开始生小母牛，所以第n年新生的牛来自于第n-3年的未成熟小母牛和成熟母牛。综上，f(n) = f(n-1) + f(n-3)特殊的，f(1)=1，f(2)=2，f(3)=3代码实现直接非递归版

function cow(n) {    if(n < 1)        return 0;    if(n === 1)        return 1;    if(n === 2)         return 2;    if(n === 3)        return 3;    var s1 = 1, s2 = 2, s3 = 3;    var res = 0;    for(var i = 4;i <= n;i++){        res = s1+s3;        s1 = s2;        s2 = s3;        s3 = res;    }        return res;}