Java描述 LeetCode，279. Perfect Squares

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

1 <= n <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares
题目比较简单，意思是给出一个数字n，从它小于的完全平方数中，进行选择，每个数字可以用无数次，问最少使用多少个数n1，n2…使得,n1+n2+n3+… = n.

从题目的几个字眼可以看出这是一道，完全背包问题，比如最少，每个数字可以用无数次。那么我们只需要处理好状态转移方程，和边界问题就可以，还记得吗？处理最小的时候，要注意java的Integer.MAX_VALUE

• dp状态：dp[j]代表构成数字j最少需要dp[j]个完全平方数。
• 状态状态转移方程：dp[j] = Math.min(dp[j],dp[j-i*i]+1)很好理解，当选中一个数的时候，其最优解，就是子问题的个数+自己本身这个数，所以+1。一个数，同样可以选择选不选，那么就有两种方案，取最小值即可。小提示，如果状态转移方程，写不出来，用一个例子模拟一下，很快就能发现，状态转移方程怎么写了，至少背包问题完全可以这么来。
• 初始化，dp[0] = 0，0个，题目的意思1，4，9 没有说到0，就不把0当作perfect square number。
• 确定遍历顺序，按照完全背包顺序，即可。

public static int numSquares(int n) {
    List list = getNum(n);
    int[] dp = new int[n + 1];
    if (n == 0) {
        return 0;
    }

    for (int i = 0; i < n + 1; i++) {
        dp[i] = i;
    }

    for (int i = 1; i < list.size(); i++) {
        for (int j = 0; j <= n; j++) {
            int num = list.get(i);
            if (j >= num) {
                dp[j] = Math.min(dp[j], dp[j - num] + 1);
            }
        }
        System.out.println(Arrays.toString(dp));
    }
    return dp[n];
}

public static List getNum(int n) {
    List list = new ArrayList<>();
    for (int i = 1; i <= n / 2; i++) {
        if (i * i <= n) {
            list.add(i * i);
        }
    }
    System.out.println(list);
    return list;
}

首先我的思路，是先找到所有的完全平方数，组成一个物品数组，这很符合常规的套路，最后再初始化第一个row，这样也不用Integer.MAX_VALUE，可以过，之后看了别人的还有更简单的代码。

public static int numSquares2(int n) {
    int[] dp = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        dp[i] = Integer.MAX_VALUE;
    }
    dp[0] = 0;
    for (int i = 0; i * i <= n; i++) {
        for (int j = i * i; j <= n; j++) {
            if (dp[j - i * i] < Integer.MAX_VALUE) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        System.out.println(Arrays.toString(dp));
    }
    return dp[n];
}

我是没想到，一边遍历一边算上完全平方数，我喜欢一步一步来，虽然代码会繁琐一点。可能是我不够聪明吧，哈哈哈哈。