70. 爬楼梯

• 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

• 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

• 思路：

  • 考虑: 假设现在已经爬到了某一阶台阶，那是如何到达这里的呢？可能是从前一阶台阶爬上来的，也可能是从前两阶台阶爬上来的。也就是说，从第 i 阶楼梯，可以从第 i - 1 或者 i - 2 阶楼梯爬上来。因此，有一个递推公式：d[i] = d[i-1] + d[i-2]

1. 动态规划

# 1. 动态规划
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 1:
            return 0
        if n == 1:
            return 1
        elif n == 2:
            return 2
        
        d = [0] * (n + 1)  
        # 初始化列表长度为 n + 1, 所有元素的值为 0, 用来存储每个台阶的爬法数
        d[1] = 1  
        # 第 1 阶只有 1 种方式
        d[2] = 2  
        # 第 2 阶有 2 种方式
        
        # 从第 3 阶开始，根据递推公式计算每个台阶的爬法数
        for i in range(3, n + 1):
            d[i] = d[i - 1] + d[i - 2]
        
        # 返回到达第 n 阶的方法数
        return d[n]

• 时间复杂度: O(n)
• 空间复杂度: O(n)

空间优化版本

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 1:
            return 0
        if n == 1:
            return 1
        elif n == 2:
            return 2
        
        # 使用两个变量来存储前两阶的爬法数
        prev1, prev2 = 2, 1  # prev1 是 d[i-1], prev2 是 d[i-2]
        
        for i in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
        
        # 返回最终的结果
        return prev1

• 时间复杂度: O(n)
• 空间复杂度: O(1)

2. 递归法

# 2. 递归(ps: 递归法在leetcode中运行会超时)
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 1:
            return 1
        return self.climbStairs(n-1) + self.climbStairs(n-2)

• 时间复杂度: O(2^n)，递归调用的过程形成了一个类似于树的结构，每一层都会有两个递归分支，导致时间复杂度呈指数级增长。总的递归调用数大约为 2^n，因此时间复杂度是 O(2^n)。
• 空间复杂度: O(n)，递归调用会在系统栈中占用空间，每一次递归都会添加一个新的栈帧，直到到达基准情况（n <= 1）。最深的递归调用栈的深度为 n（因为递归每次减少 1 或 2），所以空间复杂度是 O(n)。