279-完全平方数

​​https://leetcode-cn.com/problems/perfect-squares/​​

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

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

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

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

要求

• 1 <= n <= 104

class Solution {
    public int numSquares(int n) {
        int z = n + 20;
        int[] dp = new int[z];
        int[] tmp = new int[]{1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801, 10000};
        Map<Integer, Integer> x = new HashMap<>();
        int m = tmp.length;
        for (int i = 0; i < m; i++) {
            x.put(tmp[i], 1);
        }
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 1;
        for (int i = 4; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                int y = i + j;
                if (y < z) {
                    if (x.containsKey(y)) {
                        dp[y] = 1;
                    } else {
                        if (dp[y] == 0) {
                            dp[y] = dp[i] + dp[j];
                        } else {
                            dp[y] = Math.min(dp[i] + dp[j], dp[y]);
                        }
                    }
                }
            }
        }
        return dp[n];
    }
}      

超时了，因为这种两重循环的方式其实是有多个点被重复计算的，所以需要考虑将第二重循环进行优化，即如果我们再将动态规划递推思路思考一下，对于值i来说，等于所有i减去完全平方数的最小值加1。

class Solution {
    public int numSquares(int n) {
        int z = n + 20;
        int[] dp = new int[z];
        int[] tmp = new int[]{1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801, 10000};
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 1;
        int tmpn = tmp.length;
        for (int i = 4; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < tmpn; j++) {
                if (tmp[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - tmp[j]] + 1);
                }else {
                    break;
                }
            }
        }
        return dp[n];
    }
}      

class Solution {
    public int numSquares(int n) {
        int z = n + 20;
        int[] dp = new int[z];
        int[] tmp = new int[]{1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801, 10000};
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 1;
        int tmpn = tmp.length;
        for (int i = 4; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            int a = Integer.MAX_VALUE;
            for (int j = 0; j < tmpn; j++) {
                if (tmp[j] <= i) {
                    a = Math.min(a,dp[i-tmp[j]]);
//                    dp[i] = Math.min(dp[i], dp[i - tmp[j]] + 1);
                }else {
                    break;
                }
            }
            dp[i] = a + 1;
        }
        return dp[n];
    }
}