279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example,
Example 1:
1, 4, 9, 16, ...) which sum to n.Example 1:
Input: n =12Output: 3 Explanation:12 = 4 + 4 + 4.
Example 2:
Input: n =13Output: 2 Explanation:13 = 4 + 9.
思路：题目意思为给定一个正整数n，找到总和为n的最小正方数（例如，1,4,9,16 ……）。可以用动态规划的思想，循环里计算，每次增加一个dp数组的长度，里面那个for循环一次循环结束就算好下一个数由几个完全平方数组成，直到增加到第n+1个，返回即可。
代码如下：
public class PerfectSquares {
public static int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}