Dynamic Programming • Math

Perfect Squares

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

Overview

This problem is functionally identical to the "Coin Change" problem. In this case, the "coins" are dynamically generated perfect squares (1, 4, 9, 16...).

The DP Array

`dp[i]` stores the minimum number of squares needed to sum to `i`. We initialize the array with `Infinity` because we want to find the minimum.

The Inner Loop

For a target `i`, we test subtracting all perfect squares `j * j` that are less than or equal to `i`.

Math Optimization

While DP solves this elegantly in O(N√N), Legendre's 3-Square Theorem can actually solve this in O(√N) time mathematically!

Current Target (i)

-

Testing Square

-

DP Array (Min Squares)

0

1

∞

2

∞

3

∞

4

∞

5

∞

6

∞

7

∞

8

∞

9

∞

10

∞

11

∞

12

∞

Code Tracker

:::

1let dp = new Array(n + 1).fill(Infinity);

2dp[0] = 0;

3for (let i = 1; i <= n; i++) {

4 for (let j = 1; j * j <= i; j++) {

5 let square = j * j;

6 dp[i] = Math.min(dp[i], dp[i - square] + 1);

7 }

8}

9return dp[n];