首页 > 代码库 > leetcode-Perfect Squares-279
leetcode-Perfect Squares-279
输入整数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 };
leetcode-Perfect Squares-279
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。