The above, however, has an exponential time complexity-- that is, O(2^n). Additionally, we don't want to find all the possible perfect squares each time, that wouldn't be very time efficient.
How can we turn this into a shortest path problem? Notice the branching, too-- how might we construct a graph to help us work backwards from a sum to perfect squares? Additionally, there's the opportunity for reuse of calculations.
Well, if we used a data structure for storing the calculations-- let's say a hash, we can memo-ize the calculations. Let's imagine each key in the hash representing a number, and its corresponding value as being the minimum number of squares to arrive at it.
Alternatively, we can use an array, and simply store the sequence of perfect squares for easy lookup.
