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.