输入整数n，求完全平方数的和等于n中完全平方数用得最少的个数
直观想法搜索，先处理n以内的完全平方数，然后搜索，但效率不行，整数范围内的完全平方数有40000多个，用搜索的方法相当于求集合的子集个数，时间是2^n，肯定超时
正解：dp
dp[i]表示完全平方数和等于i的最优解
dp[i]=min(dp[i-j*j]+1)
时间N*sqrt(N)
1 class Solution { 2 public: 3 int numSquares(int n) { 4 if(n==0) return 0; 5 int dp[n+1]; 6 memset(dp,0,sizeof(dp)); 7 dp[1]=1; 8 for(int i=2;i<=n;i++){ 9 int mi=INT_MAX; 10 int ok=0; 11 for(int j=1;j*j<=i;j++){ 12 if(j*j==i){ 13 dp[i]=1; 14 ok=1; 15 break; 16 } 17 mi=min(mi,dp[i-j*j]+1); 18 } 19 if(!ok) dp[i]=mi; 20 } 21 return dp[n]; 22 } 23 };
原文：http://www.cnblogs.com/0summer/p/5831834.html