# 爬楼梯问题：常见数列的解法总结

爬楼梯问题：常见数列的解法总结

在编程中，爬楼梯问题（Climbing Stairs Problem）是一个经典的动态规划问题，常常作为入门学习动态规划和递推的重要例题。这个问题看似简单，但背后包含了多种解决方式，尤其是与 斐波那契数列 和 组合数 等数列的关系。

本文将总结几种常见的数列解法，帮助大家更好地理解爬楼梯问题的多样性和灵活性。

问题描述

假设你正在爬楼梯。每次可以爬 1 或 2 个台阶，求你有多少种不同的方法可以爬到楼顶。

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶：
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶：
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

数列解法概述

爬楼梯问题本质上可以通过不同的数列模型来解决。不同的解法可以使用以下几种常见的数列：

1. 斐波那契数列解法

斐波那契数列是最常见的解法之一。问题的递推关系是：每个台阶有两种选择：

• 从前一个台阶跳 1 个台阶
• 从前两个台阶跳 2 个台阶

所以我们可以得出以下递推公式：

dp[i] = dp[i-1] + dp[i-2]

其中 dp[i] 表示到达第 i 阶的方法数。

代码实现：

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for i in range(n - 1):
            a, b = b, a + b
        return b

解释：

• a 和 b 分别表示爬到第 i-1 阶和第 i 阶的方法数。
• 每次循环，b 更新为当前和前一个的和，即 b = a + b。
• 最终，b 就是爬到第 n 阶的方法数。

2. 动态规划解法

通过动态规划，我们可以保存中间结果，避免重复计算。这个方法适用于 n 较大时的优化。

代码实现：

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1
        for i in range(2, n + 1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

解释：

• dp[i] 表示到达第 i 阶的方法数。
• 初始化 dp[0] 和 dp[1] 为 1，因为从第 0 阶和第 1 阶都有一种方法。
• 从第 2 阶开始递推，每次累加前两个状态的值。

3. 滚动数组解法

为了进一步优化空间复杂度，我们可以使用滚动数组。只需要保存前两个台阶的结果，即可推算出当前台阶的结果，减少空间消耗。

代码实现：

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for i in range(2, n + 1):
            a, b = b, a + b
        return b

解释：

• 通过两个变量 a 和 b 代替整个 dp 数组，节省了空间。
• 每次迭代时，更新 a 和 b 的值。

4. 数学公式解法（组合数）

爬楼梯问题也可以通过组合数来解决。我们可以将问题转化为选择问题——在 n 个台阶中，有多少种方法选择其中的 k 步为 2 步。

在这种情况下，我们有：

• 选择 k 步 2 台阶，总共走 k 步 2 台阶和 n - k 步 1 台阶。
• 这个问题可以使用 组合数公式 来计算。

公式为：

C(n, k) = n! / (k! * (n - k)!)

其中 n 是台阶数，k 是选择的 2 台阶的个数。

代码实现：

import math

class Solution:
    def climbStairs(self, n: int) -> int:
        return math.comb(n, n // 2)  # 选择 n//2 步为 2 台阶

解释：

• 我们选择 n//2 步作为 2 台阶，总共会有 n - n//2 步 1 台阶。
• 使用 math.comb() 来计算组合数，得出可能的路径数。

5. 递归解法

递归解法是最直接的思路，可以通过递归计算出每个台阶的方案数，但其效率较低，适合展示算法的基本思路。由于存在大量的重复计算，递归解法的时间复杂度是指数级的。

代码实现：

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

解释：

• 每次递归都会减去 1 或 2，直到计算到达第 1 或第 2 阶。
• 这种解法可以看作是 暴力解法，时间复杂度高，适合理解递推关系。

总结

爬楼梯问题通过数列的不同解法展现了动态规划、递归和组合数等多种算法技巧。常见的解法有：

1. 斐波那契数列：通过递推关系来计算，时间复杂度 O(n)。
2. 动态规划：通过存储中间结果避免重复计算，空间复杂度 O(n)。
3. 滚动数组：进一步优化空间复杂度，空间复杂度 O(1)。
4. 组合数：通过数学公式计算，适用于考虑组合问题。
5. 递归：暴力解法，通过递归计算，时间复杂度指数级。

不同解法适用于不同的场景，在面试和实际开发中，可以根据题目的要求选择最合适的解法。

原文地址：https://blog.csdn.net/qq_17405059/article/details/145243454

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！