Optimal substructure for least number of perfect squares

Question

Question: I know how the recursion works but I can't seem to understand the 'optimal substructure' for this problem which necessitates the use of dynamic programming.

Problem: Find least number of perfect squares that sum upto a given number.

Let's say we want to find the shortest path from U to V. If we have a node X in between then shortest path from U to V will be shortest path from U to X plus shortest path from X to V.

I am having difficulty understanding how the least squares problem follows the optimal substructure property.

Answer 1

To my understanding, the recurrence relation for sum of perfect squares behaved similarly to the recurrence relation for shortest paths in the following way. Let

f(n) := minimum number of perfect squares which sum up to exactly n

then a suitable recurrence can be stated as

f(n) = min{ f(n-i) + f(i) : 0 < i < n }

which means that all partitions of the original argument into two summands have to be taken into account. Intuitively, the 'split point' for the shortest path problem is a node, whereras in the perfect squares problem it is the decision how to partition into summands (which are then examined further).

Answer 2

You did not state the property correctly, the third paragraph should be rephrased this way:

Let's say we want to find the shortest path from U to V. First verify if U and V are linked directly, if not, compute for each node X in between U and V the shortest path from U to X plus shortest path from X to V, the smallest answers will be the shortest paths from U to V, possibly duplicated.

This is applicable for your problem because you can determine the set of nodes X that are between U and V. For U=0 and V=n, this set is all the numbers from 1 to n-1, because you are adding positive numbers.

For the solution, use an array to cache the smallest path from 0 to i for i going from 0 to n, for each new value, a linear search will yield the best solutions, for an overall time complexity of O(n²).

You can optimize the linear search by enumerating only the perfect squares less or equal to n. This list is much shorter that the whole list of numbers. Its length is actually sqrt(n), so the complexity for the overall search drops to O(n^3/2).

The cache can be just a pair of integers: the length of the path and the value of an intermediary X that is on one of the shortest paths. This gives a space complexity of O(n).

The problem in question: Find least number of perfect squares that sum up to a given number. has been extensively studied for more than 17 centuries: Lagrange's four-square theorem, also known as Bachet's conjecture was already known to Diophantus in the third century. It states that every natural number can be represented as the sum of four integer squares. Analytical solutions exist for determine whether any given integer is the sum of 1, 2, 3 or 4 perfect squares.