题解 | #完全平方数的草料# 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);
            }
        }

        List<Integer> ansList = new ArrayList<>();
        while (n > 0) {
            for (int i = (int) Math.sqrt(n); i >= 1; i--) {
                if (dp[n - i * i] + 1 == dp[n] && n >= i * i) {
                    ansList.add(i * i);
                    n -= i * i;
                    break;
                }
            }
        }

        int[] ans = new int[ansList.size()];
        for (int i = 0; i < ansList.size(); i++) {
            ans[i] = ansList.get(i);
        }

        Arrays.sort(ans);
        return ans;
    }
}

编程语言是Java。

该题考察的知识点包括：

• 动态规划
• 平方根

代码的文字解释：

1. 使用 int[] dp 来表示每个数字能够由最小平方数和组成的个数。数组的大小为 n + 1。
2. 初始化状态数组：将 dp 数组的所有元素初始化为最大值。然后将 dp[0] 设为 0，表示数字 0 由 0 个平方数和组成。
3. 动态规划状态转移：遍历数组的每个位置 i，对于每个位置，通过尝试所有小于等于 i 的平方数，更新 dp[i] 的最小值。
4. 构建结果数组：使用列表 ansList 来存储最终的结果，即最小平方数和的组成。通过反向追溯，从 n 开始，不断寻找满足条件的平方数，将其加入结果列表，并减去对应的平方数值。
5. 将结果列表转化为数组：将列表 ansList 转化为数组 ans。
6. 对结果数组排序：对数组 ans 进行排序，以满足题目要求的升序顺序。
7. 返回结果数组：返回经过处理的结果数组 ans。