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.
For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Test Cases
Input:
(int) n = 12
Output:
(int) 3
Explanation:
12 = 4 + 4 + 4
Input:
(int) n = 13
Output:
(int) 2
Explanation:
12 = 4 + 9
Solution
class Solution {
public int numSquares(int n) {
int[] res = new int[n+1];
Arrays.fill(res, Integer.MAX_VALUE);
res[0] = 0;
for(int i=1; i<=n; i++) {
for(int j=1; j*j <= i; j++) {
res[i] = Math.min(res[i], res[i - j*j] + 1);
}
}
return res[n];
}
}