假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶提示：
- 1 <= n <= 45
解题：
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
return climbStairs(n-1) + climbStairs(n-2)
}又特么超时了
官方解答：
1.动态规划
func climbStairs(n int) int {
p, q, r := 0, 0, 1
for i := 1; i <= n; i++ {
p = q
q = r
r = p + q
}
return r
}2.矩阵快速幂
type matrix [2][2]int
func mul(a, b matrix) (c matrix) {
for i := 0; i < 2; i++ {
for j := 0; j < 2; j++ {
c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j]
}
}
return c
}
func pow(a matrix, n int) matrix {
res := matrix{{1, 0}, {0, 1}}
for ; n > 0; n >>= 1 {
if n&1 == 1 {
res = mul(res, a)
}
a = mul(a, a)
}
return res
}
func climbStairs(n int) int {
res := pow(matrix{{1, 1}, {1, 0}}, n)
return res[0][0]
}3.通项公式
func climbStairs(n int) int {
sqrt5 := math.Sqrt(5)
pow1 := math.Pow((1+sqrt5)/2, float64(n+1))
pow2 := math.Pow((1-sqrt5)/2, float64(n+1))
return int(math.Round((pow1 - pow2) / sqrt5))
}