That was a really cool video, have a
cow!
Daniel Andres wrote:doing table look-up that stores already found values in a 2D array
That's exactly what my program does as well. An array is a data structure that takes an integer, and returns a value associated with that integer. A two-dimensional array takes two integers and returns a value associated with the Cartesian product of those two integers. A
Map also takes one value, and returns a value associated with it.
Map<Integer, Map<Integer, Integer>> is really the same as
int[][], and calling
memorizeResult(m, n, result), is the same as performing
array[m][n] = result. I chose
Map because the size of an array needs to be known ahead of time, while a
Map can grow as needed.
But I am not that advanced yet in Java which is why I am lost in the second code you posted.
Here's the same code, except in less concise form:
When we get the final results for n, is that an indication of memory use?
The results that my program print are ALL the calculations that it stored in the table in order to compute
A(4,1) fast. It didn't store anything for
m <= 2, because those values are calculated directly from the special cases that I added on lines 18 and 19 of the original code. If I disable those lines, the memory and time used become MUCH greater. This is not an indication of peak memory usage though, because it doesn't count stack frames. Indeed, the stack will blow up much sooner than the
Map...
It's interesting that the professors in the video need so much time to calculate
A(4,1), because that would mean they're not using memoization, and they have a huge stack to be able to make the recursive calls.
If I replace all
Integers in my program with
BigIntegers and enable the special case for
(m == 3), my application is able to immediately calculate
A(4,2):
You can imagine that calculating
A(4,3) or
A(5,1) is not going to happen...