[数据结构与算法]LeetCode 热题 HOT 100——???????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 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs

思路：

这道题首先要明白，运用数学归纳法的思想，第一步可以走1级台阶，也可以走2级台阶。 如果第一步走1级台阶，剩下的台阶数为n-1，也就是说这种情况下的走法是相当于A(n-1)；同理，如果第一步走2级台阶，剩下的台阶数为n-2，这样的走法相当于A(n-2)；于是，得出：A(n) = A(n-1) + A(n-2);
?

一开始采用的是递归法，但是由于会超出时间限制，所以我用了另一种方法。（斐波那契）

var climbStairs = function(n) {
    let n1 = 1;
    let n2 = 2;
    let step = 0;
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    else {
         for (let i = 3; i <= n; i++) {
          step = n1 + n2;
          n1 = n2;
          n2 = step;
        }
    }
    return step;
};