题解 | #跳台阶#的Python解法

1. 解题思路之暴力分析法

由于题目要求一次只能跳 1个台阶或 2个台阶，所以我们可以暴力画出青蛙🐸从1阶到5阶的跳法来寻找规律，下面看图：

青蛙遇到1个台阶的时候，只有一种跳法：
青蛙遇到2个台阶的时候，有两种跳法：
青蛙遇到3个台阶的时候，有三种跳法：
青蛙遇到 4个台阶的时候，有五种跳法：
青蛙遇到 5个台阶的时候，有八种跳法：

看到这里应该大家都发现规律了👇

咦？！如果刷题很多的朋友应该马上就会发现 最后的f(n)表达式不就跟前面求NC65.斐波拉契数列一样吗！！！那么解法也就跟前面的斐波拉契数列的解法类似，不过这里的初始变量是f(1) = 1, f(2) = 2，这个需要注意一下！

2. 暴力解法的核心代码

上面的暴力解法思路转换为代码如下：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        #由于一次可以跳1个台阶或2个台阶，所以可得到
        if number < 3:
            return number
        #当台阶大于等于3的时候，f(n) = f(n - 1) + f(n - 2)
        return self.jumpFloor(number - 1) + self.jumpFloor(number - 2)

但是会出现运算超时的结果。。。

图片说明
所以当n很大的时候，暴力解法就不可取❌ ，但是它的思路却帮我们找到了跳台阶的规律。

3. 正确的动态规划解法思路

具体思路可以参考👉NC65.斐波拉契数列这篇题解的解释，已经很详细了。

4. 动态规划的核心代码

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        #由于一次可以跳1个台阶或2个台阶，所以可得到
        if number < 3:
            return number
        #当台阶大于等于3的时候
        else:
            #定义初始值为1 和 2
            a, b =1, 2
            for i in range(number - 2): 
                a, b = b, a + b     #根据f(n) = f(n-1) + f(n-2)，可得状态转移方程如左

            return b

5. 复杂度分析

时间复杂度： $O(n)$ (根据状态转移方程和边界条件，可以得到时间复杂度 O(n))
空间复杂度： $O(n)$ (新建数组需要使用 $O(n)$ 的额外空间)

----------------------------------------------我是解法二的分割线-----------------------------------------------

6.1 优化思路

由于f(n) 只和f(n−1) 与f(n−2) 有关，因此只需要初始化三个整数变量 sum, a, b ，利用辅助变量sum 使 a, b两数字交替更新即可。
这里依然要注意初始变量a，b以及sum的设置。
这样做就节省了动态规划列表的空间，因此空间复杂度降至 O(1)。
掌柜画了个简图帮助大家理解：
图片说明

6.2 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        #由于一次可以跳1个台阶或2个台阶，所以可得到
        if number < 3:
            return number
        #当台阶大于等于3的时候，定义初始值为1，1以及辅助sum为2
        a, b, sum =1, 1, 2
        for i in range(2, number): 
            a, b = b, sum     #利用辅助变量sum让a和b交替更新
            sum = a + b
        return sum

6.3 复杂度分析

时间复杂度： $O(n)$ (根据状态转移方程和边界条件，可以得到时间复杂度 $O(n)$ )
空间复杂度： $O(1)$ (由于数组的第n项只与第n -1和第n - 2项有关，所以只需要初始化三个变量a，b，sum，利用辅助变量sum来节省数组的空间，可以得到空间复杂度 $O(1)$ )