class Solution {
    public int climbStairs(int n) {
        int cache[] = new int[n + 1];
        Arrays.fill(cache, -1);
        // recur(n, cache);
        // tab(n, cache);
        // return cache[n];
        return tabOpt(n);
    }

    // Recursive Memoization 
    private int recur(int n, int cache[]) {
        if (n == 0)
            return 1;
        if (n < 0)
            return 0;
        if (cache[n] != -1)
            return cache[n];

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

    // Tabulation solution
    private int tab(int n, int cache[]) {
        cache[0] = 1;
        for (int i = 1; i <= n; i++) {
            cache[i] = cache[i - 1] + ((i - 2 >= 0) ? cache[i - 2] : 0);
        }
        return cache[n];
    }

    // Space Optimised Tabulation solution
    private int tabOpt(int n) {
        int prev = 1, prev2 = 0;
        for (int i = 1; i <= n; i++) {
            int steps = prev + prev2;
            prev2 = prev;
            prev = steps;
        }
        return prev;
    }
}