大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。

题目考察的知识点

动态规划、贪心算法

题目解答方法的文字分析

这是一个经典的动态规划问题。我们可以使用动态规划的方法来解决。

首先，我们定义一个一维数组dp，其中dp[i]表示组成i的完全平方数的最小个数。我们要找到dp[n]的值，并根据dp[n]构造返回的数组。

接下来，我们考虑状态转移方程。对于dp[i]，我们可以遍历所有小于等于i的完全平方数jj，然后更新dp[i]的值为dp[i-jj]+1。因为我们要找到最小的个数，所以我们取所有dp[i-jj]的最小值加上1。状态转移方程为： dp[i] = min(dp[i], dp[i-jj]+1);

最后，我们可以根据dp[n]的值构造返回的数组。从dp[n]开始逆推，找到每个完全平方数jj，将它加入返回的数组中，并更新n为n-jj，继续逆推，直到n为0。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    vector<int> numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX); // 创建动态规划数组dp，初始化为INT_MAX
        dp[0] = 0; // 初始化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); // 更新dp[i]的值为dp[i-j*j]+1
            }
        }

        vector<int> result;
        int num = n;

        while (num > 0) {
            for (int j = 1; j * j <= num; j++) {
                if (dp[num] == dp[num - j * j] + 1) {
                    result.push_back(j * j); // 将完全平方数j*j加入返回的数组中
                    num -= j * j; // 更新n为n-j*j，继续逆推
                    break;
                }
            }
        }

        return result;
    }
};

这东西必须j 逆序遍历

class Solution {
public:
    vector<int> numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX); // 创建动态规划数组dp，初始化为INT_MAX
        dp[0] = 0; // 初始化dp[0]为0

        for (int i = 1; i <= n; i++) {
            for (int j = sqrt(i); j >= 1; j--) { // 从sqrt(i)逆序遍历完全平方数
                dp[i] = min(dp[i], dp[i - j * j] + 1); // 更新dp[i]的值为dp[i-j*j]+1
            }
        }

        vector<int> result;
        int num = n;

        while (num > 0) {
            for (int j = sqrt(num); j >= 1; j--) { // 从sqrt(num)逆序遍历完全平方数
                if (dp[num] == dp[num - j * j] + 1) {
                    result.push_back(j * j); // 将完全平方数j*j加入返回的数组中
                    num -= j * j; // 更新n为n-j*j，继续逆推
                    break;
                }
            }
        }
        sort(result.begin(),result.end());
        return result;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！