[279] 完全平方数

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, 100);
        if(n<4){
            return n;
        }
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 1;
        if(n == 4){
            return 1;
        }
        for(int i = 5; i<=n;i++){
            int temp = sqrt(i);
            // cout<<temp<<endl;
            for(int j = sqrt(i); j >0;j--){
                dp[i] = min(dp[i], dp[i - j * j]  + 1);
            }
            // cout<<i<<": "<<dp[i]<<endl;
        }
        return dp[n];
    }
};