C++ 解法, 执行用时: 4ms, 内存消耗: 408KB, 提交时间: 2022-07-09

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int numSquares(int n) {
        // write code here
      vector<int> w = {1};
      for (int i = 2; i * i <= n ; i ++)
        w.push_back(i * i);
      
      vector<int> f(n + 1, 0x3f3f3f3f);
      f[0] = 0;
      int size = w.size();
      for (int i = 0 ; i < size ; i ++)
        for (int j = w[i]; j <= n; j ++)
           f[j] = min(f[j], f[j - w[i]] + 1);
      
      return f[n];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 412KB, 提交时间: 2022-06-13

class Solution {
  public:
    int numSquares(int n) {
        if (n < 4) {
            return n;
        }
        vector<int> v(n + 1, 10086);
        for (int i = 1; i <= n; i++) {
            if ((int)sqrt(i) * (int)sqrt(i) == i) {
                v[i] = 1;
            } else {
                for (int j = 1; j * j < i; j++) {
                    v[i] = min(v[i], v[i - j * j] + 1);
                }
            }
        }
        return v[n];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 428KB, 提交时间: 2022-04-29

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int numSquares(int n) {
        // write code here
        if (n < 4) {
            return n;
        }
        vector<int> dp(n + 1, 10000);
        for (int i = 1; i <= n; i++) {
            //int x = sqrt(i);
           if ((int)sqrt(i) * (int)sqrt(i) == i) {
               dp[i] = 1;
           } else {
               for (int j = 1; j * j < i; j++) {
                   dp[i] = min(dp[i], dp[i - j * j] + 1);
               }
           }
        }
        return dp[n];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 428KB, 提交时间: 2022-01-28

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int numSquares(int n) {
        int arr[10005];
        memset(arr,0,sizeof(arr));
        arr[0]=0;
        arr[1]=1;
        arr[2]=2;
        arr[3]=3;
        arr[4]=1;
        arr[5]=2;
        for(int i=6;i<=n;i++)
        {
            arr[i]=i;
            double SQRT=sqrt(i);
            int SQRT_INT=int(SQRT);
            if(SQRT_INT*SQRT_INT==i)
            {
                arr[i]=1;
            }
            else
            {
                for(int j=1;j*j<i;j++)
                {
                    arr[i]=min(arr[i],arr[i-j*j]+arr[j*j]);
                }
            }

            
        }
        return arr[n];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 436KB, 提交时间: 2022-01-28

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