LeetCode，Go实现爬楼梯算法
力扣题目：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
LeetCode题目源地址：https://leetcode-cn.com/problems/climbing-stairs/
解题思路
我们先列举几个例子：
- 假设有 1 级台阶，则有 1 种方法
- 爬 1 级
- 假设有 2 级台阶，则有 2 种方法
- 爬 1 级
- 爬 2 级
- 假设有 3 级台阶，则有 3 种方法
- 分别爬 1 级
- 先爬 1 级 再爬 2 级
- 先爬 2 级 再爬 1 级
可见,如果有 n 级台阶，那么方法就是前两级台阶的方法之和，即 (n-1) + (n-2)
程序实现
- 递归
首先想到的方法就是递归了
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n==2{
return 2
}
return climbStairs(n-1) + climbStairs(n-2)
}
- 动态规划方法：
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n==2{
return 2
}
a := 1
b := 2
for i:= 3; i <= n; i++{
temp := a
a = b
b = temp + a
}
return b
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-07-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
