题目描述
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入: n = 2
输出: 2
解释: 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2:
输入: n = 3
输出: 3
解释: 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
提示:
- 1 <= n <= 45
代码及注释
func climbStairs(n int) int {
// 创建一个动态规划数组dp,长度为n
dp := make([]int, n)
// 如果楼梯数n为1,直接返回1
if n == 1 {
return 1
}
// 如果楼梯数n为2,直接返回2
if n == 2 {
return 2
}
// 初始化dp数组的前两个值
dp[0], dp[1] = 1, 2
// 动态规划求解爬楼梯的路径数量
for i := 2; i < n; i++ {
dp[i] = dp[i - 1] + dp[i - 2]
}
// 返回达到顶部的不同路径数量
return dp[n - 1]
}
代码解释
这里使用动态规划的思想来解决问题:
dp[i]
表示爬到第i
级楼梯的不同路径数量。- 初始化
dp[0] = 1
和dp[1] = 2
是因为爬1级楼梯有1种方法,爬2级楼梯有2种方法。 - 对于第
i
级楼梯,它可以由前一级或前两级楼梯爬上来,所以dp[i] = dp[i - 1] + dp[i - 2]
。
最后,返回dp[n - 1]
,即爬到第n
级楼梯的不同路径数量。