LeetCode 70. 爬楼梯
题目描述
🔥 70. 爬楼梯
爬楼梯问题是一个经典的动态规划问题。假设你正在爬楼梯，楼梯有
n级台阶。每次你可以爬 1 级或 2 级台阶。请问有多少种不同的方法可以爬到楼梯的顶部？示例 1：
示例 2：
思路分析
这个问题可以使用动态规划来解决。我们可以定义一个数组
dp，其中dp[i]表示到达第i级台阶的方法数。根据题意，我们可以得出以下递推关系：
- 如果我们在第
i级台阶，可以从第i-1级台阶爬 1 级，或者从第i-2级台阶爬 2 级。- 因此，
dp[i] = dp[i-1] + dp[i-2]。初始条件为：
dp[0] = 1（没有台阶时只有一种方法，即不动）dp[1] = 1（只有一个台阶时也只有一种方法）通过这个递推关系，我们可以从底向上计算出到达第
n级台阶的方法数。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func climbStairs(n int) int {
if n <= 1 {
return 1
}
// 初始化 dp 数组
dp := make([]int, n+1)
dp[0] = 1
dp[1] = 1
// 填充 dp 数组
for i := 2; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
- 时间复杂度：O (n)，因为我们需要遍历从 2 到 n 的每一个台阶。
- 空间复杂度：O (n)，因为我们使用了一个大小为 n+1 的数组来存储每个台阶的方法数。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！