|
给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。
给出 n = 12, 返回3 因为12 = 4 + 4 + 4。
给出 n = 13, 返回2 因为13 = 4 + 9。
代码我是抄的别人的，但是要写博客还是要先看懂才行，这是用的迭代的方法，从一开一步一步逐渐迭代最终算到最后的字。可以这么理解：（我们用到的最小的平方数就是1）
1需要1个平方数，2在1的前提下+1且需要2个平方数，也就是无论你需所求得数有多大，一步一步迭代而来。
代码如下：
public static 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<=n;i++)
{
int a=(int) Math.sqrt(i);
if(a*a==i)
{
dp[i]=1;
}
else
{
for(int j=1;j*j<=i;j++)
{
dp[i]=Math.min(dp[i], dp[i-j*j]+1);
}
}
}
return dp[n];
}
public static void main(String[] args) {
int num = numSquares(8);
System.out.println(num);
}
}
| 
转播
