视频讲解：https://www.bilibili.com/video/BV12P411T7Br

https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html

1.本题确实和上一个题一样的思路，但是没考虑好怎么才能表示这个平方数，开辟了一个新数组用来存放，结果看了代码，直接就在循环里使用这个平方数即可。

CPP

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        // int n_pow = pow(n, 0.5);
        // vector<int> nums(n_pow + 1, 0);
        // for(int i = 0; i <= n_pow; i++){
        //     nums[i] = i * i;
        // }
        // for(int i = 0; i < nums.size(); i++){
        //     for(int j = nums[i]; j <= n; j++){
        //         if(dp[j - nums[i]] != INT_MAX){
        //             dp[j] = min(dp[j], dp[j - nums[i]] + 1);
        //         }
        //     }
        // }
        for(int i = 1; i * i <= n; i++){
            for(int j = i * i; j <= n; j++){
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
};