题解 | #跳台阶#

这道题考察的是递归和动态规划，但是由于题目限制空间复杂度为O(1)，所以只能使用非递归的方法

动态规划的三个步骤
1、规定数组元素的含义
2、寻找元素之间的关系
3、找出初始值

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
# 方法一：递归
# class Solution:
#     def jumpFloor(self , number: int) -> int:
#         # write code here
#         if number <= 1:
#             return 1
#         else:
#             return self.jumpFloor(number-1) + self.jumpFloor(number-2)


# 方法二：
class Solution:
    def jumpFloor(self, number: int) -> int:
        # 1、定义一个数组表示dp[i]表示青蛙跳上第i级台阶总共有多少种跳法
        # 2、元素之间的关系：第i级台阶等于第i-1和i-2级台阶之和
        # 3、初始值  dp[1] = 1, dp[0] = 0
        # 题目1<=number<=40
        if number <= 1:
            return number
        dp = [None for _ in range(number+1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3, number+1):
            dp[i] = dp[i-1] + dp[i-2]
            
        return dp[number]