青蛙跳台阶问题——《剑指offer》

问题描述

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

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

示例 1：

输入：n = 2
输出：2
示例 2：

输入：n = 7
输出：21
示例 3：

输入：n = 0
输出：1
提示：

0 <= n <= 100

思想

从第三个台阶开始，每台阶可以从它的前一个台阶或者前两个台阶跳过去。那么这个台阶的跳法种数就是前两个个台阶跳法的总和。

C++实现

class Solution {
public:
    int numWays(int n) {
        int arr[101]={0};
        arr[0]=1;  //当一个台阶也不跳时，也是一种选择
        arr[1]=1;
        arr[2]=2;

        for(int i=3;i<101;i++){
            arr[i]=(arr[i-1]+arr[i-2])%1000000007;
        }

        return arr[n];
    }
};

python实现

class Solution:
    def jumpFloor(self, number):
        arr=[1,1,2];
        
        for i in range(3,41):
            arr.append(arr[i-1]+arr[i-2])
        
        return arr[number]