本文共 2106 字，大约阅读时间需要 7 分钟。

题目原文：

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n. 题目大意： 给出正整数n，求出把n拆成最少的完全平方数之和的个数。 例如,12=4+4+4，拆出3个完全平方数，返回3. 13=4+9，最少拆出2个完全平方数，返回2. 题目分析： 方法一：（动态规划）记dp[i]为组成i的平方数的最小个数，则可以从dp[i]推到dp[i+j^2]: dp[i+j^2]=min(dp[i+j^2],dp[i]+1),即i+j^2这个数可能有更优的拆分方式是拆出j^2,否则维持原来的拆分方式。 初始化：dp[1]=1(1只能拆出1),dp[i]=i(最坏的拆分方法是把每个数i都拆成i个1，然后进一步优化 迭代过程： i=1时，更新2,5,10,17….dp(n^2+1)=2;此时dp[2]=2 i=2时，更新3,6,11,18….dp(n^2+2)=3; …… 外层循环从1到n，内层循环从i到根号n，故总复杂度O(nlogn). 方法二：（拉格朗日四平方和定理）根据Lagrange四平方定理，任何一个正整数都可以表示成不超过四个整数的平方之和。这样只需考虑什么时候返回1,2,3,4即可。 关于lagrange四平方定理的证明见。 若一个数n是4的倍数，则一直除以4化简，道理很简单，因为若k可以拆成k1+k2+k3+k4(其中ki是完全平方数或0)，则4k=4k1+4k2+4k3+4k4，其中4ki显然也是完全平方数。 如果一个数除以8余7，则一定是由4个完全平方数组成。证明见碎碎念部分。 接下来就剩下1,2,3三种情况了，暴力搜索一下1和2的情况，所以搜索{i∈Z|i∈[0,sqrt(n)]}，如果找到能开出j-i的数，则返回1或2（如果i=0或根号n，则是1，否则是2. 若找不到，则一定是3. 因为这里的暴力搜索是从0到根号n的，所以算法复杂度是O(logn)!!!!!! 源码：（language：java） 方法一：

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

方法二：

public class Solution {    public int numSquares(int n) {        while(n%4 == 0)            n/=4;        if(n%8 == 7)            return 4;        for (int a=0; a*a<=n; ++a) {            int b = (int)Math.sqrt(n - a*a);            if (a*a + b*b == n)                return func(a) + func(b);        }        return 3;    }    private int func(int a) {        return a==0?0:1;    }}

成绩：

方法一：66ms,beats 72.43%,众数68ms,6.46% 方法二：4ms,beats 97.67% Cmershen的碎碎念： 由此可见数学是科学之母，然而我不是学数学的，那些定理的证明对我来说如同天书……还有人说，@jianchao.li.fighter这个作者出的题都跟数学有关系。 2016.3.11补充步骤2的证明部分： 首先根据四平方数定理，任何正整数都可以拆成不超过4个完全平方数的和。 显然，任何完全平方数n2要么是4的倍数，要么被4除余1.（这个证明略） 假设存在正整数a1,a2使得$a_1^2+a_2^2=8k+7(k∈N)$,那么a1和a2必然一个是偶数一个是奇数，则$a_1^2+a_2^2$可表示为$4s+4t+1(s,t∈N),$是模4余1的，与模8余7矛盾。 假设存在正整数a1,a2,a3使得$a_1^2+a_2^2+a_3^2=8k+7(k∈N)$,若有一个数是奇数，另外两个数是偶数，同上易得平方和是模4余1的， 若三个数都是奇数

转载地址：http://efomb.baihongyu.com/