70. Climbing Stairs 爬楼梯

题目

你正在爬一个 n 阶的楼梯，每次你可以爬 1 或者 2步，请问有多少种不同的方式爬上去。

解析

从后往前看，很容易看出是一个递归动态规划的问题。 f(n) = f(n-1) + f(n-2)。后一个问题的解依赖前一个问题，可以从前往后解。

伪代码

f = [n]int
f[0] = 1
f[1] = 2
f[2] = f[1] + f[0]
...
f[n-1] = f[n-2] + f[n-3]
return f[n-1]

代码

func climbStairs(n int) int {
    if n == 1 {
        return 1
    }
    f:=make([]int, n)
    f[0] = 1
    f[1] = 2
    for i:=2;i<n;i++ {
        f[i] = f[i-1] + f[i-2]
    }
    return f[n-1]
}