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<int> vec; while(sqr*sqr<=n) { vec.push_back(sqr*sqr); ++sqr; } vector<int> path; int ret=INT_MAX; helper(vec,n,path,ret,0); return ret; } void helper(vector<int> &vec,int n,vector<int> &path,int &ret,int start) { if(n==0) { int len=path.size(); if(len<ret) ret=len; return; } if(n<0) return; for(int i=start;i<vec.size();++i) { if(path.size()<ret) { path.push_back(vec[i]); helper(vec,n-vec[i],path,ret,i); path.pop_back(); } else break; } } };
改进：
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]; } };
