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

考察的知识点：动态规划；

解答方法分析：

1. 创建一个大小为n+1的数组dp来保存最小完全平方数个数。初始时，将所有元素的值设置为无限大（即INT_MAX）。
2. 将dp[0]设置为0，因为组成0的最小个数为0。
3. 从1到n遍历每个数字i，对于每个数字i，再次从1遍历到i的平方根j。对于每个平方数jj，计算使得i-jj的数的最小个数，并将其与当前dp[i]的值进行比较，更新dp[i]为较小的那个。
4. 创建一个大小为dp[n]的数组res来保存由完全平方数组成的最小个数。从res数组的最后一个位置开始，逐步向前遍历，找到每个完全平方数，并将其存入res数组中。
5. 返回res数组作为最终的结果。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型vector
     */
    vector<int> numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j * j <= i; ++j) {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }
        vector<int> res(dp[n]);
        int index = res.size() - 1;
        while (n > 0) {
            for (int i = 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;
    }
};