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 numbers

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

Recurrence relation

Recurrence pattern: past lives states

Bottom-up

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
        else:
            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]

Last updated