完全平方数
- 难度： 中等
- 通过率： 39.6%
- 题目链接：https://leetcode-cn.com/problems/perfect-squares
题目描述
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n =12输出: 3 解释:12 = 4 + 4 + 4.
示例 2:
输入: n =13输出: 2 解释:13 = 4 + 9.
解法：
典型的深度优先搜索问题，给定正整数 n，然后令 i = sqrt(n) 到 1，从 n 中减去 i*i，余下的数再次做同样的操作，直到余下的数为 0 为止。
下面 dfs 中第二个参数 m，记录了上次从 n 中减去的 i*i 对应的 i 的值。下次减去的内容一定要小于等于这个数，这是剪枝策略。因为 10 = 3*3 + 1*1 而且 10 = 1*1 + 3*3。
class Solution {
public:
int numSquares(int n) {
int min_len = INT_MAX;
dfs(n, INT_MAX, 0, min_len);
return min_len;
}
void dfs(int n, int m, int len, int& min_len){
if(n == 0){
min_len = len;
return;
}
if(n < 0 || len >= min_len){
return;
}
m = min(m, static_cast<int>(sqrt(n)));
for(int i=m;i>0;i--){
dfs(n - i*i, i, len+1, min_len);
}
}
};