Perfect Squares

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


  • 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 numbers

  • Using PSN p means we have to find the minimum number of PSNs to form n - p after

Recurrence relation

dp(n)={1,āŒŠnāŒ‹Ć—āŒŠnāŒ‹=nāˆ€pāˆˆZ,p2<nāˆ§minā”(1+dp(nāˆ’p))dp(n) = \begin{cases} 1, \lfloor{\sqrt{n}}\rfloor \times \lfloor{\sqrt{n}\rfloor} = n\\ \forall p \in Z, p^2 < n \land \min(1+dp(n-p)) \end{cases}

We add 11 to dp(nāˆ’p)dp(n-p) because we are using pp as the first perfect square.

Recurrence pattern: past lives states

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


def perfect_squares(n):
    dp = {}
    for i in range(1, n + 1): # we want to iterate from [1, n]
        root = i**0.5
        if int(root)**2 == i:
            dp[i] = 1
            p = 1
            dp[i] = 10**9 # we set it to 10^9 because we are using min()
            while p**2 < i:
                dp[i] = min(dp[i], 1 + dp[i - p**2])
                p += 1
    return dp[n]

Trick: using impossibly high/low numbers to initialize dp(i)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