hardDynamic Programming 1DPure DSA~30 min
Fewest Perfect Squares Summing to N
Express a target n as a sum of perfect squares (1, 4, 9, 16, ...) using as few terms as possible.
Problem
Given an integer n, return the least number of perfect-square numbers that sum to n.
Input
A single integer n.
Output
An integer: the minimum count of perfect squares.
Constraints
- 1 <= n <= 10^4
- Squares may be reused.
- Every n has a solution (1 is a perfect square).
Examples
Example 1
Input
n = 12
Output
3
12 = 4 + 4 + 4.
Example 2
Input
n = 13
Output
2
13 = 4 + 9.