0070. 爬楼梯 #

• 标签：动态规划
• 难度：简单

题目大意 #

描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。现在给定一个整数 n。

要求：计算出有多少种不同的方法可以爬到楼顶。

说明：

• $1 \le n \le 45$。

示例：

1
2
3
4
5
6

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

解题思路 #

思路 1：动态规划 #

1. 划分阶段 #

按照台阶的层数进行划分为 0 ~ n。

2. 定义状态 #

定义状态 dp[i] 为：爬到第 i 阶台阶的方案数。

3. 状态转移方程 #

根据题目大意，每次只能爬 1 或 2 个台阶。则第 i 阶楼梯只能从第 i - 1 阶向上爬 1阶上来，或者从第 i - 2 阶向上爬 2 阶上来。所以可以推出状态转移方程为 dp[i] = dp[i - 1] + dp[i - 2]。

4. 初始条件 #

• 第 0 层台阶方案数：可以看做 1 种方法（从 0 阶向上爬 0 阶），即 dp[0] = 1。
• 第 1 层台阶方案数：1 种方法（从 0 阶向上爬 1 阶），即 dp[1] = 1。
• 第 2 层台阶方案数：2 中方法（从 0 阶向上爬 2 阶，或者从 1 阶向上爬 1 阶）。

5. 最终结果 #

根据状态定义，最终结果为 dp[n]，即爬到第 n 阶台阶（即楼顶）的方案数为 dp[n]。

思路 1：动态规划代码 #

1
2
3
4
5
6
7
8
9

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

思路 1：复杂度分析 #

• 时间复杂度：$O(n)$。一重循环遍历的时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$。用到了一维数组保存状态，所以总体空间复杂度为 $O(n)$。因为 dp[i] 的状态只依赖于 dp[i - 1] 和 dp[i - 2]，所以可以使用 3 个变量来分别表示 dp[i]、dp[i - 1]、dp[i - 2]，从而将空间复杂度优化到 $O(1)$。