279-1

class Solution {
public:
    int numSquares(int n) {
        int dp[10001];
        dp[0]=0;dp[1]=1;
        for(int i=2; i<=n; i++){
            dp[i] = 1e6;
            for(int j=1; j*j<=i; j++)
                dp[i] = min(dp[i], 1+dp[i-j*j]);
        }
        return dp[n];
    }
};