70. 爬楼梯

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶

2. 2 阶

示例 2：

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶

2. 1 阶 + 2 阶

3. 2 阶 + 1 阶

思路

对任意一第 $i$ 阶楼梯，欲爬至该阶，只有两种方法：

1. 自第 $i-1$ 阶跳 1 阶
2. 自第 $i-2$ 阶跳 2 阶

因此，该问题就转化为一个斐波那契数列式的问题，$i=(i-1)+(i-2)$。

显然递归算法的效率是不太理想的，因此我们要以迭代方式写出该算法。

代码

func climbStairs(n int) int {

// 1, 2 直接返回

if n == 1 {

return 1

}

if n == 2 {

return 2

}

// 第一阶的跳法、第二阶的跳法

pre, num := 1, 2

// 自第三阶开始迭代

for i := 3; i <= n; i++ {

// 此时为第 i 阶

// 左侧 pre = i-1, num = i

// 右侧 num = i-1, pre+num = (i-2) + (i-1)

pre, num = num, pre+num

}

return num

}