剑指 Offer 10- II. 青蛙跳台阶问题

题目描述

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例

示例1

1 2	输入：n = 2 输出：2

示例2

1 2	输入：n = 7 输出：21

示例3

1 2	输入：n = 0 输出：1

提示

0 <= n <= 100

思路

如果n=2青蛙有两种方法跳到第2级

先跳到第1级，在跳1级到第2级
直接跳到第2级

所以n=2时，有2种跳法

如果n=3青蛙有2种方法跳到第3级

先跳到第2级，在跳1级到第3级，而跳到第2级的方法上面已经求得是2种
先跳到第1级，在跳2级到第3级

所以n=3时，有3种跳法

如果n=4青蛙有2种方法跳到第4级

先跳到第3级，在跳1级到第4级，而跳到第3级的方法上面已经求得是3种
先跳到第2级，在跳2级到第4级，而跳到第3级的方法上面已经求得是2种

所以n=4时，有5种跳法

所以青蛙跳到第n级的方法有2种

先跳到第n-1级，在跳1级到第n级，而跳到第n-1级的方法上面已经求得
先跳到第n-2级，在跳2级到第n级，而跳到第n-2级的方法上面已经求得

所以设F(N)为青蛙跳到第n级的方法种数，则F(N) = F(N - 1) + F(N - 2)

转换为一个求斐波拉契第n项值的问题，参见剑指-Offer-10-I-斐波那契数列

代码

class Solution {
public:
    int numWays(int n) {
        int F0 = 1;
        int F1 = 1;
        int ans;
        if (n <= 1 )
        {
            return n;
        }
        
        for (int i = 2; i <= n; i++)
        {
            ans = (F0 + F1) % 1000000007;
            F0 = F1 % 1000000007 ;
            F1 = ans % 1000000007 ;
        }
        return ans ;
    }
};