厦门网站建设方案外包,设计专业网站有哪些,北京seo全网营销,临淄信息港题目 给定正整数 n，找到若干个完全平方数（比如：1、4、9、16、...），使得它们的和等于n。你需要让组成和的完全平方数的个数最少。 示例1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4。 示例2：
输入：n = 13
输出：2
解释：13 = 4 + 9。 解析 这道题主要考察应聘者对于…题目
给定正整数 n，找到若干个完全平方数（比如：1、4、9、16、...），使得它们的和等于n。你需要让组成和的完全平方数的个数最少。
示例1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4。
示例2：
输入：n = 13
输出：2
解释：13 = 4 + 9。 解析
这道题主要考察应聘者对于动态规划算法的理解和掌握程度，还是有一定难度的。
对于较小的数，这道题可以使用“暴力法”来尝试所有可能的组合。但在n较大时，“暴力法”的效率极其低下，因为它会重复检查许多无效的组合。另外，随着n的增大，其时间复杂度会呈指数级增长。“暴力法”的具体实现，可参考下面的示例代码。
#include iostream
#include vector
#include cmath
using namespace std;bool IsPerfectSquare(int nNumber)
{int nTemp = (int)s
