面试题10(2):青蛙跳台阶问题

题目

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

image.png

解决思路

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

代码

class Solution{
  public:
    int Fibonacci(int n)
    {
        int a = 1;
        int b = 2;
        int result = 0;
        if(n == 0)
        {
            result = 0;
        }
        else if( n == 1)
        {
            result = 1;
        }
        else if(n == 2)
        {
            result = 2;
        }
        else
        {
            for(int i = 3;i<=n;i++)
            {
                result = a+b;
                a = b;
                b = result;
            }
        }
        return result;
    }
};

完整代码见Github