279. 完全平方数

思路

这题一开始我使用的是记忆化搜索，但是会超时，后来看了题解，才发现可以用dp来解（记忆化搜索很多时候可以用dp）。

使用一个dp数组来表示完全平方数最小数量。我们可以想到一个递推公式：
遍历所有小于等于n的完全平方数i * i，那么对于当前可见的前i个完全平方数：

1. 对于小于这个完全平方数的j，dp[j]不变和上一轮一样。
2. 对于大于等于这个完全平方数的j，dp[j] = Math.min(dp[j], dp[j - i * i] + 1。表示我们尝试使用这个完全平方数，如果使用这个完全平方数之后的数量小于原数量的话。

实际上，由于每个数（物品）选的次数没有限制，所以本题是一道标准的完全背包问题。

代码

class Solution {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        for (int i = 1; i * i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                f[j] = Math.min(f[j], f[j - i * i] + 1);
            }
        }
        return f[n];
    }
}