跳台阶问题及其变种

问题描述

一个青蛙跳台阶，一次可以跳一步，也可以跳两步，则这只青蛙跳上n级台阶一共有多少种方法？

解析

类似斐波拉契数列，青蛙跳上第n级台阶，不是从第n-1级就是n-2级跳上来的，故可以转换为n-1和n-2的问题，即f(n)=f(n-1)+f(n-2)，就是一个斐波拉契数列的问题。

代码

1
2
3
4
5
6
7
8
9
int jumpStep(int n)
{
    if(n == 1)
        return 1;
    if(n == 1)
        return 2;
        
    return f(n-1) + f(n-2);
}

变种问题

一个青蛙跳台阶，一次可以最多跳n步， 求跳上n级台阶的方法。

解析

由上述可得递推公式，f(n)=f(n-1)+f(n-2)+...+f(1)+f(0)，故f(n-1)=f(n-2)+...+f(0)，以此f(n)=2f(n-1)，该情况下n>1，而n=1时，f(1)=f(0)=1，故:f(n)=2f(n-1)=2^2f(n-2)=...=2^n-1f(1)=2^n-1，而n=1也符合这个公式，因此f(n)=2^n-1

代码

1
2
3
4
int jumpStep(int n)
{
    return 1 << --n; //使用位操作更加方便
}