Given a positive integer n, find the least number of perfect square numbers (for example,
1, 4, 9, 16, ...) which sum to n.
Example：
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
解释下题目：
给定一个正整数，求出这个数能够被分成多少个平方数加起来的和，求出最少平方数的个数
1. 动态规划
实际耗时：18ms
public int numSquares(int n) {
if (n < 1) {
//error input
return -1;
}
if (n == 1 || n == 2 || n == 3) {
return n;
}
if (n == 4) {
return 1;
}
//special situation is done
//for easy, dp[1] means the number of 1,not 2.
int[] dp = new int[n + 1];
dp[0] = 0; //very important
dp[1] = 1; //1 = 1
dp[2] = 2; //2 = 1+1
dp[3] = 3; //3 = 1+1+1
dp[4] = 1; //4 = 4
for (int i = 5; i <= n; i++) {
//any integer can use 1+1+1+1.....to compose
int min = i;
for (int j = 1; ; j++) {
if (j * j > i) {
break;
}
min = Math.min(min, dp[i - j * j] + 1);
}
dp[i] = min;
}
return dp[n];
}
踩过的坑：9
一开始我想的是贪心算法，给定一个数，找到比它小的最大的平方数，然后剩下的那个继续这么做，直到最后收敛到1，2，3，4这种小的数字上，然而事实上，12就是一个反例，比12最小的平方数是9，然后剩下3，显然3和9不是最优解，因为他们需要4个数字（1+1+1+9），而（4+4+4）只需要三个数字。后来就往DP上面靠，发现12可以通过1,4,9这三个数字加点什么得到，而1,4,9都是一个数字，不一定是最大的是最优的（这道题只满足局部最优解）
