个人评价：说简单也简单=》雷同斐波那契，说难也难：如果之前没刷到，面试短时间内还真不一定能想出合适的方式
题目难度：🌟 （参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 ）
另，通常算法题会考察分析时间复杂度和空间复杂度，可参考笔者之前的文章
爬楼梯
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
解题思路
先穷举找规律，绝对是解题的不二法门
f(1) = 1
f(2) = 2
f(3) = 3
f(4) = 5
f(5) = 8
f(6) = 13
(⊙_⊙)? 这，不是斐波那契么？？没错啦，不甘心的可继续试下 f(7)=21，为什么呢？
Duang 来个本人的思路：最后一步不是 1，就是 2 是吧？
如果是假设是 f(7)，那么最后一步为1的方法有 f(6) 种，最后一步为 2 的方法有 f(5) 种
自然就是 f(n) = f(n-1) + f(n-2) 啦~ 直接上代码吧~
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
prev, curr := 1, 2
for i := 3; i <= n; i++ {
prev, curr = curr, (prev + curr)
}
return curr
}
具体详解可参考上一篇：💯【算法面试】Go题解 2.斐波那契数列
总结
相对水一篇，但还是有可借鉴的经验：
- 先穷举找规律，绝对是解题的不二法门
- 经典题的引申，把基础经典题写法记熟