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? Note: Given n will be a positive integer.

Stairs.java

class Stairs {
    static HashMap<Integer, Integer> hm;
    
    public int climbStairs(int n) {
        hm = new HashMap<>();
        hm.put(0, 1);
        
        return helper(n);
    }
    
    private int helper(int n) {
        if(n < 0)
            return 0;
        if(hm.containsKey(n))
            return hm.get(n);
        else {
            hm.put(n, helper(n-1) + helper(n-2));
        }
        return hm.get(n);
    }
}