279. 完全平方数
题目
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4.
思路
在具体实现的时候，有一个小技巧，具体见代码
代码
public int numSquares(int n
) {
int f
[] = new int[n
+1];
f
[0] = 0;
f
[1] = 1;
for(int i
=1;i
<=n
;i
++){
if(i
==1){
f
[i
] = 1;
}else{
f
[i
] = i
;
int t
= (int)Math
.floor(Math
.sqrt(i
));
for(int j
=1;j
<=t
;j
++){
f
[i
] = Math
.min(f
[i
],f
[i
-j
*j
]+1);
}
}
}
return f
[n
];
}
