跳台阶问题
题目描述
一只青蛙一次可以跳上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; }
。
