Memoized solution to Count number of ways to climb n steps Problem statement : A Child is climbing up n steps with either 1 , 2, 3 hops ..how many ways can the child climb up the stairs?

source: cracking the coding interview book.

I have two solutions the brute force and the memoized one.

Wanted to know how to improve my solution further, any issues you see with this code?

description of the code:
Brute force: basically count in a recursive manner, as there are 3 ways to reach the nth step so we count number of ways to reach each of n-1 , n-2 and n-3 steps and then sum them up to find the number of ways of reaching the nth step.

memoized solution:

we are now caching the solutions in a hashmap to reuse the solutions.

The Code: 

public class CountNWaysforSteps {

    // running time O(3 ^ n) inefficient solution 
    public static int numberOfWays(int n){

        if(n &lt; 0 ) return 0;
        if(n == 0 ) return 1;

        return numberOfWays(n-1) + numberOfWays(n-2) + numberOfWays(n-3);
    }
    //memoized solution running time O(N)
    public static int numberOfWaysMemoized(int n, Map&lt;Integer,Integer&gt; cache){

        if(n &lt; 0 ) return 0;
        if(n == 0 ) return 1;

        if(cache.containsKey(n)){
            return cache.get(n);
        }

        int calculatedNumberOFWays = numberOfWaysMemoized(n-1, cache) + numberOfWaysMemoized(n-2, cache) + numberOfWaysMemoized(n-3, cache);
        cache.put(n,calculatedNumberOFWays);
        return calculatedNumberOFWays;
    }

    public static void main(String...args){
        System.out.println(numberOfWays(5));
        System.out.println(numberOfWaysMemoized(5, new HashMap&lt;&gt;()));
    }
}
First impressions:


The dynamic approach is a good idea, but it can be improved
When a Map&lt;Integer, T&gt; is used, see if a T[] can be used instead
When doing a dynamic solution, see if you can remove the need for recursion


By applying these tricks, my suggested solution is this:

public static int numberOfWaysFast(int n) {
    if (n &lt; 2) {
        return n &gt;= 0 ? 1 : 0;
    }
    int[] cache = new int[n+1];
    cache[0] = 1;
    cache[1] = 1;
    cache[2] = 2;
    for (int i = 3; i &lt;= n; i++) {
        cache[i] = cache[i-1] + cache[i-2] + cache[i-3];
    }
    return cache[n];
}


This solution is about 50-100 times faster on my computer, and doesn't run into StackOverflowErrors for large inputs.

If you want to improve even further, you can reuse the cache array for subsequent calls, and only calculate new values when you have to. This could be applicable if you knew the maximum bound for values to be calculated, and had to rerun the function multiple times. Otherwise you could use an ArrayList&lt;Integer&gt;, but that's a tiny bit slower.

EDIT: forgot to handle input &lt;2, added some code for it.