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

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

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

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 0
输出：1

这里要记录一下小青蛙是怎么转换成斐波那契的问题的

设跳上 $n$ 级台阶有 $f(n)$ 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 $1$ 级或 $2$ 级台阶。

• 当跳上 $1$ 级台阶时： 之前共跳了 $n-1$ 个台阶，此情况有 $f(n-1)$ 种跳法；
• 当跳上 $2$ 级台阶时： 之前共跳了 $n-2$ 个台阶，此情况有 $f(n-2)$ 种跳法。

$f(n)$ 为以上两种情况的和，即 $f(n)=f(n-1)+f(n-2)$，则该递推性质为斐波那契数列。本题可转化为 求斐波那契数列第 $n$ 项的值，与 求斐波那契数列 等价，唯一的不同在于起始数字不同。

• 青蛙跳台阶问题： $f(0)=1$ , $f(1)=1$ , $f(2)=2$ ；
• 斐波那契数列问题： $f(0)=0$ , $f(1)=1$ , $f(2)=1$ 。

class Solution:
    def numWays(self, n: int) -> int:
        a, b = 1, 1

        for _ in range(n):
            sum = (a + b) % 1000000007
            a, b = b, sum
        
        result = a % 1000000007
        return result