Leetcode递归系列(java)：70. 爬楼梯

leetcode

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

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

递归的经典题，假设一共有n个楼梯，走法一共为f(n)中，考虑上最后一个台阶的方法为两种，一次走一个或一次走两个，所以f(n)为这两种方法之和，如果最后走一个，那么前面剩余n-1个台阶，那剩余n-1个台阶的走法为f(n-1),同理最后一次走两个台阶前n-2个台阶的走法为f(n-2);所以f(n)=f(n-1)+f(n-2),一直一直套娃直到终止条件n=1或n=2。

但此题有时间限制，纯用递归的方法求解的话会超时，所以建立一个hashmap来存储每次计算的结果避免重复计算，比如走五个台阶，f(3)会计算两次，我把f(3)结果存入hashmap中，第二次用到的时候直接取出来即可。以此来减少计算量。

class Solution {
    private static Map store = new HashMap<>();
    public int climbStairs(int n) {
        int res = f(n);
        return res;
    }
    static int f(int n){
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        if(store.get(n) != null){
            return store.get(n);
        }
        int res = f(n-1)+f(n-2);
        store.put(n,res);
        return res;
    }
    

}