题目描述：给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。

方法1：动态规划，dp[i] = min(dp[i],dp[i-x]+1);x是任意小于n的完全平方数

class Solution {
public:
    int numSquares(int n) {
        vector<int> temp;
        int i=1;
        temp.push_back(0);
        while(i*i < n){
            temp.push_back(i*i);
            i++;
        }//存小于n的所有完全平方数
        vector<int> dp(n+1);//dp数组
        for(int i=0;i<dp.size();i++){
            dp[i] = i;
        }//初始化dp数组
        for(int i=1;i<dp.size();i++){
            for(int j=1;j<temp.size();j++){
                if(i < temp[j]) break;
                dp[i] = min(dp[i],dp[i-temp[j]]+1);
            }
        }
        return dp[n];
    }
};

无法通过所有样例，对本身就是完全平方数的样例会报错，原因：temp数组中的(i*i < n)应该改为(i*i <= n)

方法二：优化，可以不用创建数组存放完全平方数

class Solution {
public:
    int numSquares(int n) {
        vector<int> temp;
        int i=1;
        vector<int> dp(n+1);
        for(int i=0;i<dp.size();i++){
            dp[i] = i;
        }

        for(int i=1;i<dp.size();i++){
            for(int j=1;j*j <= i;j++){
                dp[i] = min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
};