j
2
j^2
j2是完全平方数,
i
−
j
2
i - j^2
i−j2表示第一个数选择
j
2
j^2
j2,通过dp[
i
−
j
2
i - j^2
i−j2]获取减去第一个数字后,剩余的数所需最少完全平方数 min(dp[i -
j
2
j^2
j2])的含义就是,不断尝试不同的完全平方数作为第一个,并获取剩余数字所需最少完全平方数,找到所需数字最少的一个方案。 当剩余数字
i
−
j
2
i-j^2
i−j2最少方案找到后,+1即可,因为我们前面减去了
j
2
j^2
j2,现在需要将
j
2
j^2
j2这个数字算上一个
dp数组初始化
数组遍历顺序(单重循环,无需考虑遍历顺序,一共就一维,哪里来的谁先谁后)
打印dp数组(自己生成dp数组后,将dp数组输出看看,是否和自己预想的一样。)
代码
classSolution{publicintnumSquares(int n){int[] f =newint[n +1];//dp数组,代表和为i的完全平方数最少数量。下标i表示求谁的所需完全平方数最少数量for(int i =1; i <= n; i++){//1到n开始规划每个数字的完全平方数最少数量int minn =Integer.MAX_VALUE;for(int j =1; j * j <= i; j++){//j表示完全平方数,从1开始,1,4,9,16....,但是不能>i//是否选择当前完全平方数。如果选择当前完全平方数,则i - 当前完全平方数,看看剩余数字的所需完全平方数数量//如果选择当前完全平方数所需数量更少(更优),就令minn = f[i - j*j],否则不选择当前数。minn不变
minn =Math.min(minn, f[i - j * j]);}
f[i]= minn +1;//当前数字所需的最少完全平方数数量。}return f[n];//返回n的最少所需完全平方数数量}}
四平方和定理
四平方和定理:任意正整数x,可被最多4个正整数的平方和(完全平方数)表示。
结论一:当
n
=
4
k
∗
(
8
∗
m
+
7
)
n = 4^k * (8*m + 7)
n=4k∗(8∗m+7)时,n只能被4个正整数的平方和表示。
这是一个判断条件,k和m表示随便一个数,只要n能满足即可。可以说只要
n
满足
4
k
∗
(
8
∗
m
+
7
)
n 满足 4^k * (8*m + 7)
n满足4k∗(8∗m+7)这样的条件,n就只能被4个正整数平方和表示
结论二:当前仅当
n
≠
4
k
∗
(
8
∗
m
+
7
)
n \not = 4^k * (8*m + 7)
n=4k∗(8∗m+7)时,n才可以被3个及以下(至多3个)正整数平方和表示
解题思路:时间复杂度O(
n
\sqrt{n}
n),空间复杂度O(
1
1
1)
当
n
=
4
k
∗
(
8
∗
m
+
7
)
n = 4^k * (8*m + 7)
n=4k∗(8∗m+7)时,直接返回4,因为满足这个条件的正整数只能被4个完全平方数表示
当
n
≠
4
k
∗
(
8
∗
m
+
7
)
n \not = 4^k * (8*m + 7)
n=4k∗(8∗m+7)时,则需要额外处理,因为它表示n可能被1个或2个或3个完全平方数表示。
若当前n正好是完全平方数,则答案为1,也就是它本身表示自己
若n不是完全平方数,枚举两个完全平方数,查看是否可以组成n,也就是
n
=
a
2
+
b
2
n = a^2 + b^2
n=a2+b2.枚举需要时间复杂度为O(
n
\sqrt{n}
n)
因为需要枚举一个完全平方数a,a属于[1,
n
\sqrt{n}
n], 并判断
n
−
a
2
n - a^2
n−a2是否是完全平方数
以上两个条件都不满足,则需要3个完全平方数表示,返回3即可
代码
classSolution{// 判断是否为完全平方数,如果是完全平方数,则只需1个完全平方数(它本身)即可表示publicbooleanisPerfectSquare(int x){int y =(int)Math.sqrt(x);return y * y == x;}// 判断是否能表示为 4^k*(8m+7)publicbooleancheckAnswer4(int x){while(x %4==0) x /=4;//不断除以4,相当于不断进行4^(k-1)操作,直到k归0//此时剩余(8m+7),我们取余8,则剩下的数字为不可以被8取余的数//如果剩下的数字正好是7,这返回true,否则返回falsereturn x %8==7;}publicintnumSquares(int n){if(isPerfectSquare(n))return1;//如果n是完全平方数,返回1if(checkAnswer4(n))return4;//满足n = 4^k * (8*m + 7),则只能由4个完全平方数表示//不满足n = 4^k * (8*m + 7),并且n本身不是完全平方数,则只能由2个或者3个完全平方数表示//先试图用2个完全平方数表示n,如果成功,返回2for(int i =1; i * i <= n; i++){//选择i*i作为当前完全平方数的其中之一,int j = n - i * i;//则减去这个完全平方数,剩下的数字为n - i * iif(isPerfectSquare(j))return2;//如果剩下的数字也是完全平方数,则可以由2个数字表示}//无法用2个完全平方数表示,返回3return3;}}