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

动态规划的思想，青蛙每次可以跳一个或两个台阶，要想得到最终青蛙跳n阶台阶的方法数，需要找到青蛙跳n-1个台阶的方法数和跳n-2个台阶的方法数。
想法一：
通过台阶数进行循环，以初始条件n为0和1时，方法数为1，逐步累加得到最终的结果。

class Solution:
    def numWays(self, n: int) -> int:
        # 初始条件是跳上第0阶和第1阶跳法为1
        a,b = 1,1

        # 动态规划状态转移方程为：当前元素数值为前两个元素的和
        for _ in range(n):
            a,b = b, a+b
            
        return a % 1000000007

想法二：
通过递归的方法得到结果，LeetCode上超出时间限制。

class Solution:
    def numWays(self, n: int) -> int:
        def f(n):
            if n == 0 or n == 1:
                return 1
            return f(n-1)+f(n-2)
        return f(n) % 1000000007