Represent natural number as sum of squares using dynamic programming

Question

The problem is to find the minimum number of squares required to sum to a number n.

Some examples:

min[1] = 1 = 12

min[2] = 2 = 12 + 12

min[4] = 1 = 22

min[13] = 2 = 32 + 22

I'm aware of Lagrange's four-square theorem that says that any natural number can be represented as the sum of four squares.

I'm trying to solve this using DP.

This is what I came up with (its not correct)

min[i] = 1 where i is a square number

min[i] = min(min[i - 1] + 1, 1 + min[i - prev]) where prev is a square number < i

What is the correct DP way to solve this ?

Answer 1

Seems to me that you're close...

You're taking the min() of two terms, each of which is min[i - p] + 1, where p is either 1 or some other square < i.

To fix this, just take the min() of min[i - p] + 1 over all p (where p is a square < i).

That would be a correct way. There may be a faster way.

Also, it might aid readability if you give min[] and min() different names. :-)

P.S. the above approach requires that you memoize min[], either explicitly, or as part of your DP framework. Otherwise, the complexity of the algorithm, due to recursion, would be something like O(sqrt(n)!) :-p though the average case might be a lot better.

P.P.S. See @Nikita's answer for a nice implementation. To which I would add the following optimizations... (I'm not nitpicking his implementation -- he presented it as a simple one.)

1. Check whether n is a perfect square, before entering the outer loop: if so, min[n] = 1 and we're done.
2. Check whether i is a perfect square before entering the inner loop: if so, min[i] = 1, and skip the inner loop.
3. Break out of the inner loop if min[i] has been set to 2, because it won't get better (if it could be done with one square, we would never have entered the inner loop, thanks to the previous optimization).
4. I wonder if the termination condition on the inner loop can be changed to reduce the number of iterations, e.g. j*j*2 <= i or even j*j*4 <= i. I think so but I haven't got my head completely around it.

5. For large i, it would be faster to compute a limit for j before the inner loop, and compare j directly to it for the loop termination condition, rather than squaring j on every inner loop iteration. E.g.

   float sqrti = Math.sqrt(i);
   for (int j = 1; j <= sqrti; ++j) {
   

   On the other hand, you need j^2 for the recursion step anyway, so as long as you store it, you might as well use it.

Answer 2

I'm not sure if DP is the most efficient way to solve this problem, but you asked for DP.

min[i] = min(min[i - 1] + 1, 1 + min[i - prev]) where prev is a square number < i
This is close, I would write condition as

min[i] = min(1 + min[i - prev]) for each square number 'prev <= i'

Note, that for each i you need to check different possible values of prev.

Here's simple implementation in Java.

    Arrays.fill(min, Integer.MAX_VALUE);
    min[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j*j <= i; ++j) {
            min[i] = Math.min(min[i], min[i - j*j] + 1);
        }
    }