LeetCode70 爬楼梯

假设你正在爬楼梯。需要 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. 方法一：递归。
   1. n阶，如果第一次跳一阶，那么剩余的跳阶次数就是f(n - 1) 。如果第一次跳两阶，那么剩余的跳阶次数就是f(n - 2)。那么结果就是 f(n-1) + f(n - 2）。
   2. 这里 n=1,n=2时，结果分别为1和1.那么这两种情况就是递归的终止情况。
   3. 循环体就是f(n)=f(n-1) + f(n-2)
   4. 这里注意一个方法要再递归两次。容易超时。这里可以做一个优化，f(n) = f(n - 1) + f(n - 2)，那么在计算f(n-2)的时候，f(n-1)及之前的都已经计算过了，没必要再计算一遍。可以使用额外内存空间，记录已经算过的值。减少递归次数。
2. 方法二：循环。

   n = 1, res = 1
   n = 2, res = 2
   n = 3, res = 3
   n = 4, res = 5
   n = 5, res = 8
   ...
   f(n) = f(n - 1) + f(n - 2)

   1. 按照规律，可以看出，f(n) = f(n - 1) + f(n - 2)。即，当前项结果，就是前两项之和。

// 方法一
class Solution {
    Map<Integer, Integer> tempRes = new HashMap<>();
    public int climbStairs(int n) {
        if (n < 3) {
            return n;
        }
        if (tempRes.containsKey(n)) {
            return tempRes.get(n);
        }
        int x = climbStairs(n - 1) + climbStairs(n - 2);
        tempRes.put(n, x);
        return x;
    }
}

 // 方法二
class Solution {
    public int climbStairs(int n) {
        int a = 0;
        int b = 0;
        int c = 1;
        for (int i = 0; i < n; i++) {
            a = b;
            b = c;
            c = a + b;
        }
        return c;
    }
}