跳台阶问题

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n阶台阶总共有多少中跳法。

解答：

我们可以把 n级台阶时的跳法看成是n的函数，记为 f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的 n-1级台阶的跳法数目，即为 f(n-1)；另外一种选择是跳一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为 f(n-2)。因此n级台阶的不同跳法的总数 f(n) = f(n-1) + f(n-2)。

分析到这里，我们不难看出这实际上就是斐波那契数列。

# n为台阶级数,n>0
def JumpFloor(n):
    tempArray = [1,2]
    if n>=3:
        for i in range(3, n+1):
            tempArray[(i+1)%2] = tempArray[0] + tempArray[1]
    return tempArray[(n+1)%2]      for i in range(1,6):
    print(JumpFloor(i))

int jumpFloor(int number) {
    if(number<=2)        
        return number;
    else
    {
        int a[]={1, 2};
        for(int i=3; i<=number; i++)
        {
            int tmp = a[0];
            a[0] = a[1];
            a[1] = a[0] + tmp;
        }
        return a[1];
    }
}

def JumpFloor(number):
    if(number<=0):
        return -1;
    if(number==1 or number==2):
        return number;
    return JumpFloor(number-1) + JumpFloor(number-2)

结果为：

1
2
3
5
8

变态跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

假设f(n)是n个台阶跳的次数。

• f(1) = 1
• f(2) ：有两种跳的方式，一次1阶或者2阶，即f(2) = f(2-1) + f(2-2)
• f(3) ：有三种跳的方式，1阶、2阶、3阶，那么就是f(3) = f(3-1)+f(3-2)+f(3-3)
  …
• f(n)：有n种跳的方式，1阶、2阶…n阶，得出结论：
  f(n) = f(0) + f(1) + f(2) + f(3) + … + f(n-1)
  ==> f(n) - f(n-1) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) = f(n-1)
  ==> f(n) = 2*f(n-1)

找到了规律，代码也就不难写了
和上面的类似，把return的结果改成2f(n-1)就行了

return 2*JumpFloor(number-1)