0070. 爬楼梯

0070. 爬楼梯 #

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

题目大意 #

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

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

说明

  • $1 \le n \le 45$。

示例

1
2
3
4
5
6
输入n = 3
输出3
解释有三种方法可以爬到楼顶
1. 1+ 1+ 12. 1+ 23. 2+ 1

解题思路 #

思路 1:动态规划 #

1. 划分阶段 #

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

2. 定义状态 #

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

3. 状态转移方程 #

根据题目大意,每次只能爬 12 个台阶。则第 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)$。
本站总访问量  次  |  您是本站第  位访问者