279 Perfect Squares

题意：定义perfect squares number 为(1,4,9,16,...) 给出一个正整数n，返回和为n的最小的perfect squares number 的数目。

例如：n=12 ，返回3， 因为 12=4+4+4 ；

            n=13，返回2，因为13=4+9 。

分析：动态规划，squares[i]表示i的最小perfect squares number，时间复杂度为O(n^(3/2))

代码：

class Solution {
public:
    int numSquares(int n) {
        vector<int> squares(n+1,0);
        for(int i=1;i<=n;++i){
            squares[i]=i;
            for(int j=1;j*j<=i;++j){
                    squares[i]=min(1+squares[i-j*j],squares[i]);
            }
        }
        return squares[n];
    }
};