【图解版】力扣第70题：爬楼梯
推理出状态表达式
-
f(5)表示到达第5层，所有可能的方法数。
-
到达第5层，有可能是从第4层走一步上来，也有可能是从第3层走两步上来。所以我们可以慢慢延伸，画出上面👆🏻的图。
-
从图中，我们可以看到，这些路径，就像这个树的每一个分支，只要数一下有多少个分支，那到第5层就有多少种路径。
-
f(4)表示了到达第4层的路径数量总和，f(3)表示到达第3层的路径数量的总和，所以f(5)的总数量：
f(5) = f(4) + f(3)。 -
总结：
f(n) = f(n - 1) + f(n - 2)
Golang代码实现
- 代码实现的逻辑跟上面树状图的逻辑有点不太一样，上面只是得出
f(n) = f(n - 1) + f(n - 2)的结论，这里是进行爬楼梯具体的代码实现，用到的是滚动的做法。
func climbStairs(n int) int {
// 如果只有一层和两层，就直接返回n就行，题目规定1 <= n <= 45
if n <= 2 {
return n
}
// f1表示走到第一层可能有的方法数： 1种，直接走一步。总体上f1是表示f(n - 2)
// f2表示走到第二层可能有的方法数：2种，走两步 or 走一步，再走一步。总体上f2是表示f(n - 1)
// fn表示走到第n层可能有的方法数，初始化为0。总体上fn是表示f(n)
f1, f2, fn := 1, 2, 0
for i := 3; i <= n; i++ { // 从第3层开始计算，计算到第n层刚好结束
fn = f1 + f2 // f(n) = f(n - 2) + f(n - 1)
f1 = f2 // f(n - 1)替换前面那个f(n - 2)，成为新的f(n - 2)
f2 = fn // f(n) 替换前面那个f(n - 1)。成为新的f(n - 1)
}
return fn
}