C++面试宝典第27题：完全平方数之和

题目

给定正整数 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