Hanoi’s cache problem and connection to fibonacci

Personally, I experienced a lot of difficulties solving the Hanoi's problem with the caching feature, so hopefully this serves as helpful tip.

I was stuck on the memorization problem for days until I finally drew the recursion on a piece of paper. I was able to convince myself that generally for problems like recursion or dynamic programming, the relevant subproblems were already solved.

You should not hold on to any _cache entry longer than needed for a 1-time calculation with a given number of discs (think like you need to calculate fibonacci(n)) -You will have to call vector::clear() on some levels as you descend

For example: Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2). We first check if Fib(n) is already there (in that case, we would simply use the stored value of Fib(n), and wouldn't be deleted),

and if not, we would use the Fib(n-1) and Fib(n-2) to compute Fib(n) and store Fib(n), then immediately dispose Fib(n-1) and Fib(n-2).

I think this is what it means to have a 1-time calculation.

When calling Fib(n-1) and Fib(n-2), it goes through the same process and thus the answer is already stored before we add them to get Fib(n), and we can only get rid of them after calculating Fib(n).