题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9 7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1
提示：
0 <= n <= 100
解析：
这道题和爬楼梯一模一样，和斐波那契数列特别相似，不过就是初始条件不太相同而已，主要将这个问题化为两个子问题，跳上1级台阶和跳上2级台阶，而总的跳法是这两个子问题的和。这样就有两种方法，一种递归法，一种动态规划法。
第一种：递归法，递归终止条件是n==0和1，都返回1即可。而斐波那契数列则 是0和1，略有不同。
#1.递归的方式
def numWays(n: int) -> int:
if n == 0:
return 1
if n == 1:
return 1
return (numWays(n-1) numWays(n-2)) %int(1000000007)
第二种：动态规划法（推荐），这个问题是典型的动态规划问题，通过求解子问题的最优解来获得全局问题的最优解。解决了递归法的重复计算问题。
青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。
1，当为 1 级台阶： 剩 n-1 个台阶，此情况共有 f(n-1)种跳法；
2，当为 2 级台阶： 剩 n-2个台阶，此情况共有 f(n-2)种跳法；
总跳法为以上两种情况之和，即 f(n)=f(n-1) f(n-2) ；
#2.典型动态规划题
def numWays2(n: int) -> int:
if n == 0 or n==1:
return 1
dp = [0]*(n 1)
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3,n 1):
dp[i] = dp[i-1] dp[i-2]
return dp[-1] %int(1000000007)
执行结果：
输入7
