Perfect Squares

Use a shortest-composition recurrence

Let dp[i] be the minimum number of perfect squares summing to i. Set dp[0] = 0 and initialize other entries to a large sentinel. For each amount i, try every square j*j <= i and relax dp[i] = min(dp[i], dp[i-j*j] + 1). Squares are reusable, so the recurrence naturally supports repeated use.

There are n amounts and about sqrt(n) candidate squares each, yielding O(n sqrt(n)) time and O(n) space. A BFS interpretation over remainders also works, but the DP is simpler for one target. Test n = 0, a perfect square, sums requiring several terms, and values near integer-square boundaries. Never use plain recursion without memoization because it repeats subproblems exponentially. If asked only for the mathematical minimum rather than construction, number-theory shortcuts exist, but explain their preconditions and keep the DP as a dependable baseline.