1.题目

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

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

示例 1：

输入： 2

输出： 2

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

1 阶 + 1 阶

2 阶

示例 2：

输入： 3

输出： 3

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

1 阶 + 1 阶 + 1 阶

1 阶 + 2 阶

2 阶 + 1 阶

2.答题

2.1 思路1（递归）

很明显能看出可以用递归解决，将问题拆分成更小的子问题来解决

递推公式：f(n) = f(n – 1) + f(n – 2)
终止条件：当n==1时，只有1种走法，当n==2时，可以有（1、1）和（2）两种走法

代码如下：

class Solution {
    public int climbStairs(int n) {
        if(n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}
复制代码

提交未通过，当n==45时超出时间限制，正好可以提醒警惕递归可能出现的问题：

警惕堆栈溢出

函数调用使用栈来计算保持临时变量，每一次递归调用产生的临时变量，会以栈帧的形式压入内存栈，当递归层次过深时，可能导致堆栈溢出。

警惕重复计算

本题中的计算过程，f(5) = f(4) + f(3)，f(6) = f(5) + f(4)，两个过程都分别计算了f(5)、 f(4)，其他层次也使用了重复的计算，这就造成了浪费的情况，所以可以使用缓存来避免重复计算。

改造后的代码：

class Solution {
    Map<Integer, Integer> mCache = new HashMap<>();
    public int climbStairs(int n) {
        if(n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        if (mCache.containsKey(n)) {
            return mCache.get(n);
        }

        int cache = climbStairs(n - 1) + climbStairs(n - 2);
        mCache.put(n, cache);
        return cache;
    }
}
复制代码