Perfect Squares
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself (e.g., 1, 4, 9, 16, ...).
Examples
Input: 12
Output: 3
Input: 13
Output: 2
Hints
Consider the mathematical theorem that every natural number can be represented as a sum of four integer squares (Lagrange's four-square theorem). Can you use this to optimize your solution?
Instead of checking all perfect squares up to `n`, can you precompute them once and reuse them for all `i` in the DP loop?
Can you further optimize the DP approach by leveraging the fact that the answer for `n` is at most 4 (due to Lagrange's theorem), and thus limit the search space for `j` in the inner loop?
Related Problems
Perfect Squares
Given an integer `n`, return the least number of perfect square numbers that sum to `n`.