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

动态规划

1. 创建一个长度为n+1的整数数组dp，用来存储计算最小个数的中间结果。初始时，将数组中的所有元素都设置为最大值Integer.MAX_VALUE，除了dp[0]设置为0，表示组成0的最小个数为0。
2. 使用两层循环来填充动态规划数组dp。外层循环遍历1到n的每个数，内层循环遍历1到当前数的平方根，计算当前数的最小个数。对于每个内层循环的迭代，通过比较dp[i]和dp[i - j * j] + 1的值，更新dp[i]为较小的那个。
3. 创建一个整数数组res来存储最终的结果。初始化一个变量index为res数组的长度减1。
4. 遍历数组dp，从n开始递减，找到每个平方数对应的最小个数。内层循环从当前数的平方根开始，迭代递减，检查是否满足n >= i * i且dp[n] == dp[n - i * i] + 1的条件，如果满足，则将当前平方数i * i放入res数组的index位置，index递减，同时更新n为n - i * i。重复此过程直到n变为0。
5. 由于i*i是按照index递减存放故不需要再次排序

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型一维数组
     */
    public int[] numSquares (int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        //组成0的最小个数为0
        dp[0] = 0;

        //计算组成当前数的最小个数
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j * j <= i; ++j) {
                //j*j为一个完全平方数+dp[i],求最小组和个数
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        int[] res = new int[dp[n]];
        int index = res.length - 1;
        while (n > 0) {
            for (int i = (int) Math.sqrt(n); i > 0; --i) {
                // 每一个完全平方数都是当前数的最小组合数之一
                if (n >= i * i && dp[n] == dp[n - i * i] + 1) {
                    res[index--] = i * i;
                    n -= i * i;
                    break;
                }
            }
        }
        return res;
    }
}