题解 | #最少的完全平方数#

bool check(int n){
    return n == (int)sqrt(n) * sqrt(n);
}
int numSquares(int n) {
    // write code here
    vector<int> dp(n+1,INT_MAX);
    for(int i=1;i<=n;i++)
        if(check(i))
            dp[i]=1;
        else{    
            for(int j=1;j<=i/2;j++)
                dp[i] = min(dp[i], dp[j] + dp[i-j]);
        }
    return dp[n];
}