题解 | #完全平方数的草料#

题目考察的知识点是：

动态规划。

题目解答方法的文字分析：

定义一个数组 dp，其中 dp[i] 表示构成数字 i 所需的最小完全平方数数量。然后，我们从 1 到 n 枚举每一个数字 i，计算其对应的 dp 值。具体来说，对于每个数字 i，我们枚举所有小于等于它的完全 平方数 j^2，然后计算 dp[i-j^2]+1 的最小值。这个最小值即为 dp[i] 的值。最后，我们可以通过倒推的方式，从 dp[n] 开始向前找到第一个满足条件的完全平方数，并将其加入结果列表。然后更新当前数字为 n 减去这个完全平方数的差，继续寻找下一个完全平方数，直到 n 等于 0。

本题解析所用的编程语言：

java语言。

完整且正确的编程代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型一维数组
     */
    public int[] numSquares (int n) {
        // write code here
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        int[] ans = new int[dp[n]];
        int index = ans.length - 1;
        while (n > 0) {
            for (int i = (int) Math.sqrt(n); i >= 1; i--) {
                if (dp[n - i * i] + 1 == dp[n] && n >= i * i) {
                    ans[index] = i * i;
                    index--;
                    n -= i * i;
                    break;
                }
            }
        }
        return ans;
    }
}