假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
输入:
输出:
解释: 有两种方法可以爬到楼顶。
. 阶 + 阶
. 阶 输入:
输出:
解释: 有三种方法可以爬到楼顶。
. 阶 + 阶 + 阶
. 阶 + 阶
. 阶 + 阶
乍看这道题,以为是求解1和2的随机组合=n的问题,但是我们先来看看下面的表格:
n | 没有2的情况 | 有1个2的情况 | 有2个2的情况 | 有3个2的情况 | 总数 |
---|---|---|---|---|---|
1 | 1 | 1 | |||
2 | 1 | 1 | 2 | ||
3 | 1 | 2 | 3 | ||
4 | 1 | 3 | 1 | 5 | |
5 | 1 | 4 | 3 | 8 | |
6 | 1 | 5 | 6 | 1 | 13 |
从表格看出其实是一个斐波那契数列,那么代码就很简单了
//斐波那契数列
func climbStairs(n int) int {
sli := []int{, , }
if n <= {
return sli[n-]
}
for i := ; i < n; i++ {
sli = append(sli, sli[i-]+sli[i-])
}
return sli[len(sli)-]
}