[Leetcode] Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

递归+memory，其实就是DP的方法，比较基础的题目。

    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    public int climbStairs(int n) {
        if(n == 0 || n == 1) return 1;
        else {
            if(map.containsKey(n) == true) {
                return map.get(n);
            }
            else {
                int step = climbStairs(n-1) + climbStairs(n-2);
                map.put(n, step);
                return step;
            }
        }
    }