Memoized solution to Count number of ways to climb n steps
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.