Minimum Perfect Squares

Problem

Return the minimum number of perfect squares that sum to n, where squares may repeat.

Use DP where dp[i] tries every square j * j <= i and keeps 1 + dp[i - j * j]. By Lagrange's theorem the answer is never larger than 4.

Hint

The worst case uses only 1s, so initialise dp[i] with i.

case 1

in: [12]

expected: 3

case 2

in: [13]

expected: 2

case 3

in: [1]

expected: 1

case 4

in: [0]

expected: 0

case 5

in: [100]

expected: 1

case 6

in: [27]

expected: 3

Starter codePython

def min_perfect_squares(n):
    # Your code here
    pass

6 test cases · run your code against them in the editor