刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/climbing-stairs/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

假设你正在爬楼梯。需要 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

思路

这个其实就是斐波那契数列。

或者按照动态规划的思路来考虑:

• 上第一阶时，只有一种方式，上一阶。
• 上第二阶时，有两种方式，上两次一阶和上一次二阶。
• 上第三阶时，可能从第一阶上去，也可能从第二阶上去，所以其实就是上第一阶的次数加上上第二阶的次数
• 以此类推得到公式 f(x) = f(x-1) + f(x-2)

上代码。

代码

func climbStairs(n int) int {
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}
    // x_2 代表 `f(x-2)`， x_1 代表 `f(x-1)`，num 用来存储`f(x)`
	x_2, x_1, num := 1, 2, 0
	for i:=3; i<=n; i++ {
		num = x_1 + x_2
		x_2 = x_1
		x_1 = num
	}
	return num
}