作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
假设你正在爬楼梯。需要 n 步你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 将是一个正整数。
输入格式
- n：一个正整数，表示楼梯的总台阶数。
输出格式
- 返回一个整数，表示不同的爬楼梯方法数。
示例
示例 1
输入: n = 2 输出: 2 解释: 有两种方法可以爬到楼顶。 1. 1 步 + 1 步 2. 2 步
示例 2
输入: n = 3 输出: 3 解释: 有三种方法可以爬到楼顶。 1. 1 步 + 1 步 + 1 步 2. 1 步 + 2 步 3. 2 步 + 1 步
方法一：动态规划
解题步骤
- 定义状态数组：
dp[i]表示到达第i阶楼梯的方法数。 - 初始化：
dp[0] = 1（不动），dp[1] = 1（一步）。 - 状态转移方程：
dp[i] = dp[i-1] + dp[i-2]。 - 求解：计算
dp[n]。
完整的规范代码
def climbStairs(n): """ 使用动态规划解决爬楼梯问题 :param n: int, 楼梯总步数 :return: int, 爬到楼顶的方法数 """ if n <= 1: return 1 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] # 示例调用 print(climbStairs(2)) # 输出: 2 print(climbStairs(3)) # 输出: 3
算法分析
- 时间复杂度：(O(n))，一次遍历到
n。 - 空间复杂度：(O(n))，用于存储
dp数组。
方法二：空间优化的动态规划
解题步骤
- 利用两个变量滚动更新：只需要两个变量来存储前两步的结果。
- 更新变量：迭代更新两个变量来计算下一步的值。
完整的规范代码
def climbStairs(n): """ 使用空间优化的动态规划解决爬楼梯问题 :param n: int, 楼梯总步数 :return: int, 爬到楼顶的方法数 """ if n <= 1: return 1 a, b = 1, 1 for i in range(2, n + 1): a, b = b, a + b return b # 示例调用 print(climbStairs(2)) # 输出: 2 print(climbStairs(3)) # 输出: 3
算法分析
- 时间复杂度：(O(n))。
- 空间复杂度：(O(1))，只使用固定的几个变量。
方法三：矩阵快速幂
解题步骤
- 定义转移矩阵：使用矩阵快速幂求解斐波那契数列问题。
- 矩阵乘法：定义矩阵乘法和矩阵快速幂函数。
完整的规范代码
def climbStairs(n): """ 使用矩阵快速幂解决爬楼梯问题 :param n: int, 楼梯总步数 :return: int, 爬到楼顶的方法数 """ if n <= 1: return 1 def multiply(a, b): return [[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]], [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]] def matrix_pow(matrix, power): result = [[1, 0], [0, 1]] base = matrix while power: if power % 2: result = multiply(result, base) base = multiply(base, base) power //= 2 return result result = matrix_pow([[1, 1], [1, 0]], n - 1) return result[0][0] + result[0][1] # 示例调用 print(climbStairs(2)) # 输出: 2 print(climbStairs(3)) # 输出: 3
算法分析
- 时间复杂度：(O(log n))，矩阵快速幂的时间复杂度。
- 空间复杂度：(O(1))，使用了常数空间来存储矩阵和中间结果。
方法四：斐波那契公式
解题步骤
完整的规范代码
import math def climbStairs(n): """ 使用斐波那契公式解决爬楼梯问题 :param n: int, 楼梯总步数 :return: int, 爬到楼顶的方法数 """ sqrt5 = math.sqrt(5) fib_n = (((1 + sqrt5) / 2) ** (n + 1) - ((1 - sqrt5) / 2) ** (n + 1)) / sqrt5 return int(fib_n) # 示例调用 print(climbStairs(2)) # 输出: 2 print(climbStairs(3)) # 输出: 3
算法分析
- 时间复杂度：(O(1))，直接计算。
- 空间复杂度：(O(1))，不需要额外的存储空间。
方法五：递归加记忆化
解题步骤
- 递归定义：定义递归函数来计算
f(n)。 - 记忆化：使用哈希表存储已计算的结果，避免重复计算。
- 递归计算：通过递归调用计算爬楼梯的方法数，并存储结果。
完整的规范代码
def climbStairs(n): """ 使用递归加记忆化解决爬楼梯问题 :param n: int, 楼梯总步数 :return: int, 爬到楼顶的方法数 """ memo = {1: 1, 2: 2} def recursive(n): if n not in memo: memo[n] = recursive(n - 1) + recursive(n - 2) return memo[n] return recursive(n) # 示例调用 print(climbStairs(2)) # 输出: 2 print(climbStairs(3)) # 输出: 3
算法分析
- 时间复杂度：(O(n))，递归中每个数值只计算一次。
- 空间复杂度：(O(n))，存储递归过程中的中间结果和递归栈。
不同算法的优劣势对比
| 特征 | 方法一：动态规划 | 方法二：空间优化动态规划 | 方法三：矩阵快速幂 | 方法四：斐波那契公式 | 方法五：递归加记忆化 |
| 时间复杂度 | (O(n)) | (O(n)) | (O(log n)) | (O(1)) | (O(n)) |
| 空间复杂度 | (O(n)) | (O(1)) | (O(1)) | (O(1)) | (O(n)) |
| 优势 | 易于理解和实现 | 更节省空间 | 较快的计算时间 | 最快的计算效率 | 避免了冗余计算 |
| 劣势 | 较高的空间占用 | 没有明显劣势 | 实现复杂 | 精度问题可能影响结果 | 递归深度大时可能溢出 |
应用示例
计算理论研究：这些方法在计算理论和算法研究中非常有用，特别是在学习如何处理递归问题和优化问题解决方案的过程中。例如，在学术课程或算法竞赛中，不同的解决方案可以帮助理解各种算法技术的应用和优化。
软件开发：在软件开发中，如游戏程序或者路径规划算法中，这些方法可以用来解决实际问题，如寻找最优路径或者计算到达某个目标的不同方式，提高程序的效率和响应速度。
欢迎关注微信公众号 数据分析螺丝钉
