Day 4 : 279 Perfect Squares

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is a number that's obtained by multiplying an integer by itself (e.g. 1=1×1, 4=2×2, 9=3×3).

Before we get started let's take a deep breath…

It took me some good time to wrap my head around this problem, so let’s take it step by step!

• What are we asked? Find minimum number of perfect squares needed to sum to n
  (e.g., 12 = 4+4+4, answer is 3)

• What do we need to calculate each element? For each number i, check dp[i - perfectSquare] + 1 where perfectSquare ≤ i .

• Base cases: dp[0] = 0 (empty sum) dp[1] = 1 (1 × 1)

Let's look at an example with n = 13.

The sequence builds up like this:

1. dp[1] = 1 (1)

2. dp[2] = 2 (1+1)

3. dp[3] = 3 (1+1+1)

4. dp[4] = 1 (4)

5. dp[5] = 2 (4+1)

6. dp[13] = 2 (4+9)

So for n = 13, answer is 2 because 13 = 4 + 9

We will use dynamic programming to solve this problem. If you need a refresher from the last problem.

Top-Down Approach

There's a very basic template for most top-down recursive approaches!

1. Base case: Define when to stop recursion (at the smallest subproblems)!

2. Memoization: If computation was previously done and stored, just retrieve it!

3. Formula: If computation wasn't done before, compute and save result!

For example, with n = 12: Break down the problems:

First, obtain all perfect squares that are lower or equal to 12:

• 0 x 0 = 0

• 1 x 1 = 1

• 2 x 2 = 4

• 3 x 3 = 9 

Once we have calculated the perfect squares smaller than n, we’ll use an auxiliary function that breaks n = 12 into smaller subproblems.

To do so, we will set a minSquares variable which contains our answer and since we want to minimize it, we set it to MAX_INT.

Then we will iterate through the previously computed perfect squares. For each square that is smaller than n, we will find which is smaller, what we currently have or the remainder of what we have left + our current perfect square.

Let me explain that a little better.

The formula min(minSquares, 1 + dfs(n - square)) means:

• 1 + counts the perfect square we just used

• dfs(n - square) recursively finds best solution for remaining amount

• min(minSquares, ...) keeps track of best solution found so far

Now, for every perfect square let's compute answer for each n

• dp[12] = min( dp[12 - 9], dp[12 - 4], dp[12 - 1] ) + 1

• dp[11] = min( dp[11 - 9], dp[11 - 4], dp[11 - 1] ) + 1

• dp[10] = min( dp[10 - 9], dp[10 - 4], dp[10 - 1] ) + 1

• dp[9] = min( dp[9 - 9], dp[9 - 4], dp[9 - 1] ) + 1

And so on until we reach dp[0] and dp[1], our base cases!

After reaching them, we will be able to build the result back up with recursion:

• dp[1] = 1

• dp[2] = min(1) + 1 = 1 + 1 = 2

• dp[3] = min(2) + 1 = 2 + 1 = 3

• dp[4] = min(2, 0) + 1 = 0 + 1 = 1

And so on until we are back at our result, dp[12] !

Below is an example for n = 4 !

class Solution {
    vector<int> dp;
    vector<int> perfectSquares;
    
    void precomputeSquares(int n) {
        // Precompute all perfect squares <= n
        for (int i = 1; i * i <= n; i++) {
            perfectSquares.push_back(i * i);
        }
    }
    
    int dfs(int n) {
        // Base cases
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        // If already calculated
        if (dp[n] != -1) return dp[n];
        
        int minSquares = INT_MAX;
        // Use precomputed perfect squares
        for (int square : perfectSquares) {
            if (square > n) break;  
            minSquares = min(minSquares, 1 + dfs(n - square));
        }
        
        dp[n] = minSquares;
        return minSquares;
    }
    
public:
    int numSquares(int n) {
        dp.resize(n + 1, -1);
        precomputeSquares(n);  
        return dfs(n);
    }
};

Bottom-Up Approach

The only difference is we will build iteratively from the base cases to bigger problems until we have solved our main problem! So we start by solving our base cases, and up from there!

We start by initializing an array dp where dp[i] represents the minimum number of perfect squares needed to sum to i

We’ll set dp[0] = 0 as our base case and initialize all other values to infinity (since we want to minimize).

Then comes the fun part 🥳 , building the array back up.

We solve this one number at a time, from 1 up to our target n. For each number i:

1. We consider every perfect square (1², 2², 3², etc.) that's less than or equal to i

2. For each such perfect square, we try using it and add 1 to the solution for the remaining value

3. Keep track of the minimum result found

To keep track of the minimum result found, we will:

• dp[i] - current best solution for making number i

• j * j - perfect square we're trying to use (1, 4, 9, etc.)

• i - j*j - what's left after using this perfect square

• dp[i - j*j] - best solution for the remaining amount

• + 1 - counts using the current perfect square

• min(...) - keeps the better of the two options

int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;  // base case
        
        // For each number from 1 to n
        for (int i = 1; i <= n; i++) {
            // Try each perfect square less than or equal to i
            for (int j = 1; j * j <= i; j++) {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }
        
        return dp[n];
    }
};

Resources of the week

• This year give the best gift ever!!! 

• Your safest way to wealth as a SWE!!

Self-hacks of the week

I truly believe you can gaslight yourself to success.

1. Interviews don’t filter out talent, they filter out preparation: A LeetCode problem a day, keeps unemployment away ✨ 

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!