# Perfect Squares

There is a purely mathematical solution for this as well but I won't cover it here

## Observations

The number of perfect square numbers (PSN) that sum to a perfect square is

`1`

The minimum number of PSNs to form

`n`

is found by trying all possible combinations of perfect square numbersUsing PSN

`p`

means we have to find the minimum number of PSNs to form`n - p`

after

## Recurrence relation

We add $1$ to $dp(n-p)$ because we are using $p$ as the first perfect square.

**Recurrence pattern:** past ~~lives~~ states

Some states rely on multiple previously computed state. This contrasts the $n$ state caching optimization as $n$ is not fixed.

## Bottom-up

**Trick: **using impossibly high/low numbers to initialize $dp(i)$
If `min(dp[i], ...)`

is used, then use an impossibly high number to initialize `dp[i]`

Otherwise, if `max(dp[i], ...)`

is used, then use an impossibly low number or `0`

if no other states can be `0`

.

Last updated