题解 | #跳台阶#

标签：动态规划

1. 解题思路参照：https://blog.nowcoder.net/n/d94de17162f74cc1bd858af7c551324d

2. 规律：

• 从第2项开始（n为3时），满足：f(n) = f(n-1) + f(n-2)
• 如果使用递归方式实现，会超时，时间复杂度为O(n^2)。代码如：

class Solution:
    def jumpFloor(self, number: int) -> int:
        if number == 1:
            return 1
        elif number == 2:
            return 2
        else:
            return self.jumpFloor(number - 1) + self.jumpFloor(number - 2)

• 优化点：每次遍历n时，将n项的值保存、并做累加；同时更新下一项的前两项值。

3. 优化后代码：

时间复杂度：O(n)

空间复杂度：O(1)

class Solution:
    def jumpFloor(self, number: int) -> int:
        if number <= 2:
            return number
        a = 1
        b = 2
        result = 0
        # 第三项开始是前两项的和,然后保留最新的两项，更新数据相加
        for i in range(3, number + 1):
            result = a + b
            a = b
            b = result
        return result