### Python 实现爬楼梯问题 #### 动态规划方法 动态规划是一种解决该问题的有效方式。通过构建数组 `dp` 来存储每一步的结果，从而避免重复计算。以下是基于动态规划的实现代码： ```python class Solution: def climbStairs(self, n): if n == 1: return 1 dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] if __name__ == '__main__': num = 7 solu = Solution().climbStairs(num) print(solu) # 输出结果为 21 ``` 此代码的时间复杂度为 O(n)，空间复杂度也为 O(n)[^1]。 #### 使用优化的空间复杂度 可以进一步优化空间复杂度至 O(1)，仅需两个变量来保存前两步的状态即可： ```python def climbStairs_optimized(n): if n == 1: return 1 first, second = 1, 2 for _ in range(3, n + 1): third = first + second first, second = second, third return second if __name__ == '__main__': num = 7 result = climbStairs_optimized(num) print(result) # 输出结果为 21 ``` 这种方法同样具有时间复杂度 O(n)，但其空间复杂度降低到 O(1)[^1]。 #### 递归方法 虽然递归方法直观易懂，但由于存在大量重复计算，效率较低。可以通过记忆化技术改进性能： ```python adict = {} def func(n): if n == 1 or n == 2: return n if adict.get(n, None) is not None: return adict[n] else: result = func(n - 1) + func(n - 2) adict[n] = result return result if __name__ == '__main__': num = 6 print(func(num)) # 输出结果为 8 ``` 这段代码利用字典缓存中间结果，有效减少了冗余计算[^3]。 #### 斐波那契数列关系 爬楼梯问题本质上是一个斐波那契数列的应用场景。因此也可以直接调用斐波那契函数解决问题： ```python def fibonacci_climb_stairs(n): a, b = 1, 2 for _ in range(3, n + 1): a, b = b, a + b return b if n >= 2 else a if __name__ == '__main__': num = 7 print(fibonacci_climb_stairs(num)) # 输出结果为 21 ``` 这种解法与第二种动态规划方案类似，均采用迭代形式完成计算[^1]。 ---