Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

超时：

class Solution {public:    int numSquares(int n) {        if(n<=0)            return 0;        int sqr=1;        vector
     
       vec;        while(sqr*sqr<=n)        {            vec.push_back(sqr*sqr);            ++sqr;        }        vector
      
        path;        int ret=INT_MAX;        helper(vec,n,path,ret,0);        return ret;    }    void helper(vector
       
         &vec,int n,vector
        
          &path,int &ret,int start)    {        if(n==0)        {            int len=path.size();            if(len
        
       
      
     

改进：

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