算法：爬楼梯

这题也是经典动态规划题。

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 阶或 2 阶。
问有多少种不同的方法可以爬到楼顶？

一、思路

到第 n 阶时，最后一步只有两种情况：

• 从第 n-1 阶爬 1 步上来
• 从第 n-2 阶爬 2 步上来

所以：

f(n) = f(n-1) + f(n-2)

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

二、状态转移

定义：

f(i) = 到达第 i 阶的方法数

则：

f(i) = f(i-1) + f(i-2)

初始条件：

f(1) = 1 f(2) = 2

三、代码实现

1. 动态规划

function climbStairs(n) { if