题目 :
假如你正在爬楼梯。须要 n 阶你能力达到楼顶。
每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢?
链接:力扣 Leetcode—高级算法—动静布局—爬楼梯.
示例 1 :
输出:n = 2
输入:2
解释:有两种办法能够爬到楼顶。
(1) 1 阶 + 1 阶
(2) 2 阶
示例 2 :
输出:n = 3
输入:3
解释:有三种办法能够爬到楼顶。
(1) 1 阶 + 1 阶 + 1 阶
(2) 1 阶 + 2 阶
(3) 2 阶 + 1 阶
标签:记忆化搜寻、数学、动静布局
思路:咱们先来画一个表格,这样能够更容易的看出解题思路
n | 办法 | 总和 |
---|---|---|
1 | 1 | 1 |
2 | 1+1 2 | 2 |
3 | 1+1+1 1+2 2+1 | 3 |
4 | 1+1+1+1 1+2+1 1+1+2 2+1+1 2+2 | 5 |
5 | 1+1+1+1+1 1+2+1+1 1+1+2+1 1+1+1+2 2+1+1+1 1+2+2 2+1+2 2+2+1 | 8 |
… | … | … |
从表格看出其实是一个斐波那契数列,须要走 n 阶你能力达到楼顶,每次只能爬 1 或 2 个台阶,不同的办法总数就等于 [(n- 1 阶总办法数)+(n- 2 阶总办法数)],那么代码就很简略了,先定义切片寄存 n =1,2,3 的时候的总办法数,再从 3 开始,遍历到总台阶数为 n,用 append 办法始终给切片(slice)追加元素,追加到 sli[i-1]+sli[i-2],返回 len(sli)-1 就是不同办法数的总和。
次要 Go 代码如下:
package main
import "fmt"
// fibonacci 数列(斐波那契数列)func climbStairs(n int) int {sli := []int{1, 2, 3}
if n <= 3 {return sli[n-1]
}
for i := 3; i < n; i++ {sli = append(sli, sli[i-1]+sli[i-2])
}
return sli[len(sli)-1]
}
func main() {
n := 5
fmt.Println(climbStairs(n))
}
提交截图: