When I ran it on IDEONE, it gave the exception
Exception in thread “main” java.lang.OutOfMemoryError: Java heap space
at Main.main(Main.java:18)
A hint… I only memoised part of the range, and used recursion for the rest of it.
A question… why do you create a new DP cache with each test case? Will the numbers stored in DP change between cases?