Perfect Squares

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

---

This question is the same as Coin Change.

The problem is requiring the minimum number of perfect squares that sum to the target value.

If we were looking for any number of perfect squares, or every combination of perfect squares that sum to the target value, then that would make this problem a candidate for backtracking to generate these sums.

However, if we wanted to utilize that approach for this problem, we would be calculating the same values multiple times which would make the algorithm inefficient for what we're trying to do.

A better approach is to use Dynamic Programming so that we can refer back to subproblems that have been calculated prior to avoid recalculating them.

The subproblems will be each number from one to n, in which we will find the minimum number of squares that sum to that value.

---

Let's start by creating an array of squares that we'll be trying to sum to the target.

The squares we'll be choosing are each square up to the square root of the target number.  Anything greater than that would be impossible to fit into the sum because we aren't using any negative numbers.

        squares = []
        for i in range(1, int(n**(1/2)) + 1):
            squares.append(i**2)

 

Next, we'll create our dp lookup table.

We will initialize each element to be infinity, with the exception of the zeroth index, since we would be using zero squares to sum to zero.  This is our base case.

We want to use infinity since it is out of the bounds of our possible amounts, and we can ensure that the square amounts we will use to overwrite these will be lower in value.

        dp = [0] + [float("inf")] * n

 

Here is where the bottom-up processing logic will come into play.

We are going to create an outer loop to traverse the squares, an inner loop to traverse from the current square amount to the n input, and within the inner loop, we are going to set the value in the current index as the minimum between what it already is, or the value in the index at the current iterator, minus the square amount, plus one.

        for square in squares:
            for i in range(square, n+1):
                dp[i] = min(dp[i], dp[i-square]+1)

 

So let's explain what this is going to do given the squares of [1,4,9], and an n of ten.

The lookup table, dp is telling us the minimum possible square amount for each target amount.  In other words, index one holds the minimum amount of squares needed to sum to an n of one, index two for an n of two, etc.  

This is how we can break this problem up into subproblems and avoid recalculating the same values.

We will start off at index one and step all the way to the tenth index, adding ones to each previous index since that is the minimum amount of squares we can sum to the current subproblem if we were only using ones.

Our lookup table will look like this after the first pass.

0

1

2

3

4

5

6

7

8

9

10

 

Once we are done handling each subproblem using only the first perfect square, we can grab the next one, four, and begin clarifying subproblem values from index four onward. There is no point in trying to include a four at any index before four because each of the previous amount values is less than four.

So how many fours should we put in each index?  That is where our lookup table comes in handy.  

In the line of code given below, we are basically saying that we will either keep the value that we already have, or we will take the value in the current index minus the square amount, then add one to it.

                dp[i] = min(dp[i], dp[i-square]+1)

 

For example, let's say we are at index four.  We had written four in it previously, so that means we had four ones that we dropped in it from the last pass. 

Should we keep the four ones, or what dp[i-square] has, then add one to it?  Well, dp[0] is zero, if we add one then we will have one.  Is one less than four?  Yes, so we remove the four ones and drop a four at index four.  We'll also remove four ones and drop a nickel from index five through ten as well for the same reason, and afterward, our dp table will look like this.

0

1

2

3

1

2

3

4

2

1

4

 

Lastly, we will see if we can get a lower amount of squares at index ten once we iterate to the nine from our squares array.

0

1

2

3

1

2

3

4

2

1

2

 

Once we are finished, we will return the last element of the table which contains the minimum number of squares needed to sum to the target amount given.

        return dp[-1]

---