题目

解法：动态规划

思路

第一段：使用动态规划，定义 dp[i] 表示凑出数值 i 所需的最少完全平方数个数，通过枚举所有可能的平方数进行状态转移。

第二段：该方法正确性的核心在于最优子结构性质。对于任意数值 i，若选择使用一个完全平方数 j²，则剩余部分 i-j² 的最优解加上当前这一个数，就构成了 i 的一个可行解。由于我们枚举了所有可能的 j² 并取最小值，因此 dp[i] 必然保存了全局最优解。dp[0]=0 作为基础边界条件，保证了递推链条的正确启动。

第三段：

• Step 1: 初始化 dp 数组，dp[0]=0，其余元素初始化为 INF
• Step 2: 外层循环遍历 i 从 1 到 n
• Step 3: 内层循环遍历 j 从 1 到 √i，枚举所有可用的完全平方数
• Step 4: 状态转移：dp[i] = min(dp[i], dp[i - j*j] + 1)
• Step 5: 返回 dp[n] 作为最终结果

复杂度

• 时间复杂度: $O(n \sqrt{n})$
• 空间复杂度: $O(n)$

代码

class Solution {
public:
    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);

            }
        }

        return dp[n];
    }
};