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.

    public int climbStairs(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        int start1 = 1;
        int start2 = 2;
        int count = 0;
        for (int i = 3; i <= n; i++) {
            count = start1 + start2;
            start1 = start2;
            start2 = count;
        }
        return count;
    }

    private HashMap<Integer, Integer> mCache = new HashMap<>();

    public int climbStairs(int n) {
        if (mCache.containsKey(n))
            return mCache.get(n);
        if (n > 2) {
            int c = climbStairs(n - 1) + climbStairs(n - 2);
            mCache.put(n, c);
            return c;
        }
        if (n == 2)
            return 2;
        else if (n == 1)
            return 1;
        return 0;
    }