本文主要是介绍leetcode279 拉格朗日四平方和定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4.
拉格朗日四平方和定理：
1、对于任意一个正整数都可以表示成至多四个整数的平方和(把0考虑进去了也)
下面剪枝性的来找对任意正整数n可以表示成多少几个整数的平方和
2、 若k%4=0,则 k和n具有相同个数的整数和表示
3、 若n%8=7,则 n可以被表示为4个整数的平方和 n=4^a*(8b+7)
int init(){while(n%4==0){n/=4;} if(n%8==7) return 4;for(int i=0;i*i<=n;++i){int j=sqrt(n- i*i);if(j*j == n-i*i){return !!i + !!j; //找1或 2的形式 } }return 3;
}看讨论区有个用bfs来搜，从n搜到0，看完后敲了dfs,对于有些数复杂度爆炸
int dfs(int n){if(!n)return 0;if(sqrt(n)*sqrt(n)==n){return 1;}int cnt=0x3f3f3f;for(int i=1;i*i<=n;++i){cnt=min(cnt,dfs(n-i*i)+1);}return cnt;
}bfs可以这样理解：给出一个正整数n找到若干个完全平平方数使得n减去他们的差为0，求最少的完全平方数
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6;
const int inf=0x3f3f3f3f;
int dp[maxn];
int a[maxn];
int n;
int cnt;
void bfs(){queue< pair<int,int> >Q;Q.push(make_pair(n,0) );vector<bool> vis(n,false);vis[n]=true;while(!Q.empty()){int num= Q.front().first;int step= Q.front().second;Q.pop();for(int i=1;i*i<=num;++i){int a=num - i*i;if(a<0) break;else if( a== 0) {cnt =step+1;return ;}else{if(!vis[a]){Q.push(make_pair(a,step+1));vis[a]=true;}}}}
}
int main(){while(scanf("%d",&n)!=EOF){bfs();cout<<cnt<<endl;}return 0;
}
递推性的dp
memset(dp,maxn,sizeof(dp));dp[0]=0;for(int i=1;i<=n;++i){for(int j=1;j*j<=i;++j){dp[i]=min(dp[i],dp[i-j*j]+1);}}cout<<dp[n]<<endl;
这篇关于leetcode279 拉格朗日四平方和定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
