/*
Runtime: 0 ms, faster than 100.00% of Java online submissions for Climbing Stairs.
Memory Usage: 33 MB, less than 5.26% of Java online submissions for Climbing Stairs.
*/
class Solution {
    public int climbStairs(int n) {
        if (n < 0) return 0;

        int[] cache = new int[n + 1];
        return climb(n, cache);
    }

    private int climb(int n, int[] cache) {
        if (n <= 1) return 1;

        if (cache[n] > 0) {
            return cache[n];
        }

        int result = climb(n - 2, cache) + climb(n - 1, cache);
        cache[n] = result;
        return result;
    }
}