【Java题解】279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和
11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

方法一:
动态规划。

1. n减去一个完全平方数，然后取减去后的值包含的最少的完全平方数的个数 + 1，设为：x
2. n减去另外一个完全平方数，然后取减去后的值包含的最少的完全平方数的个数 + 1，设为：y
3. 取min(x, y)
4. 循环操作，直到减完了所有可以减去的完全平方数，即，再减就小于当前的值n了。

代码：

class Solution {
	// 这样操作是为了剪枝，用list来记录对应坐标值，包含的最少平方数
	// 的个数。
    static ArrayList list = new ArrayList<>();
    public int numSquares(int n) {
        // 放入dp一个初始值
        if (list.size() == 0) {
            list.add(0);
        }
        if (list.size() <= n) {
            for (int i = list.size(); i <= n; i++) {
                int count = Integer.MAX_VALUE;
                for (int j = 1; j * j <= i; j++) {
                    count = Math.min(count, list.get(i - (j * j)) + 1);
                }
                list.add(count);
            }
        }
        return list.get(n);
    }
}

时间复杂度：O(n * sqrt(n)) 从双层循环哪里可以看出。
空间复杂度：O(n)