279.完全平方数

喜喜这个自己做的

class Solution {
public:
    int numSquares(int n) {
        // dp[i] 和为 i 的完全平方数的最少数量 
        // dp[j] = min(dp[j],dp[j-i*i]+1)
        vector<int>dp(1+n,INT_MAX);
        dp[0]=0;
        for(int i = 1; i * i <= n; i ++ ) {
            for(int j = i*i; j <= n; j ++ ) {
                dp[j] = min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
};