Description
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Solution
DP, time O(n * sqrt(n)), space O(n)
本来以为会有什么dark magic，随便写了个DP就过啦竟然。
class Solution {
public int numSquares(int n) {
int[] count = new int[n + 1];
count[0] = 0;
for (int i = 1; i <= n; ++i) {
count[i] = i; // made up with 1
for (int j = (int) Math.sqrt(i); j > 0; --j) {
count[i] = Math.min(count[i], 1 + count[i - j * j]);
}
}
return count[n];
}
}
