题解 05| #跳台阶#

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param number int整型
# @return int整型
class Solution:
    def jumpFloor(self, number: int) -> int:
        if number <= 2:
            return number
        a,b=1,2
        for i in range(3,number+1):
            a,b=b,a+b
        return b
b=Solution()
print(b.jumpFloor(7))

一、解题思路

1. 理解问题：青蛙一次跳1或2级台阶，求跳n级台阶共有多少种跳法
2. 分析问题：分析不同级数台阶的跳法数关系（n级台阶的跳法数等于n-1级和n-2级台阶跳法数之和），发现可以用动态规划来解决这个问题
3. 设计算法：选用动态规划方法，创建一个列表来存储每个子问题（每个级数上的跳法数量），这样在计算n级台阶时，可以利用之前已计算的结果
4. 编写代码：将分析和设计的算法用python编写为一个函数
5. 测试优化：使用不同输入测试实现方法，并调整算法优化性能，降低时间复杂度或空间复杂度

二、举一反三

如果青蛙能跳1级、2级、3级，求跳n级台阶共有多少种跳法

def three_num(n):

if n<3:

return max(1,n)

a,b,c=1,1,2

for i in range(3,n+1):

a,b,c=b,c,a+b+c

return c

print(three_num(int(input())))

• 当 n = 0 时，跳法数= 1（青蛙不跳，直接站在 0 级台阶上）
• 当 n = 1 时，跳法数 = 1（直接跳 1 级台阶）
• 当 n = 2 时，跳法数 = 2（分两种情况：1 级+1 级 台阶 或 直接跳 2 级台阶）
• 当 n = 3 时，跳法数 = 4（分四种情况：1 级+1 级+1 级 或 3 级 台阶 或 1 级+2 级 台阶 或 2 级+1 级 台阶）

设 F(n) 表示跳上 n 级台阶的跳法数，则递推关系为：

F(n) = F(n-1) + F(n-2) + F(n-3)