# 0279. 完全平方数
### 题目地址(279. 完全平方数)
### 题目描述
```
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
```
### 前置知识
* 递归
* 动态规划
### 公司
* 阿里
* 百度
* 字节
### 思路
直接递归处理即可，但是这种暴力的解法很容易超时。如果你把递归的过程化成一棵树的话（其实就是递归树）， 可以看出中间有很多重复的计算。
如果能将重复的计算缓存下来，说不定能够解决时间复杂度太高的问题。
> 递归对内存的要求也很高， 如果数字非常大，也会面临爆栈的风险，将递归转化为循环可以解决。
递归 + 缓存的方式代码如下：
```js
const mapper = {};
function d(n, level) {
if (n === 0) return level;
let i = 1;
const arr = [];
while (n - i * i >= 0) {
const hit = mapper[n - i * i];
if (hit) {
arr.push(hit + level);
} else {
const depth = d(n - i * i, level + 1) - level;
mapper[n - i * i] = depth;
arr.push(depth + level);
}
i++;
}
return Math.min(...arr);
}
/**
* @param {number} n
* @return {number}
*/
var numSquares = function (n) {
return d(n, 0);
};
```
如果使用 DP，其实本质上和递归 + 缓存 差不多。
DP 的代码见代码区。
### 关键点解析
* 如果用递归 + 缓存， 缓存的设计很重要 我的做法是 key 就是 n，value 是以 n 为起点，到达底端的深度。 下次取出缓存的时候用当前的 level + 存的深度 就是我们想要的 level.
* 使用动态规划的核心点还是选和不选的问题
```js
for (let i = 1; i <= n; i++) {
for (let j = 1; j * j <= i; j++) {
// 不选（dp[i]） 还是 选（dp[i - j * j]）
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
```
### 代码
代码支持：CPP，JS
CPP Code:
```cpp
class Solution {
public:
int numSquares(int n) {
static vector dp{0};
while (dp.size() <= n) {
int m = dp.size(), minVal = INT_MAX;
for (int i = 1; i * i <= m; ++i) minVal = min(minVal, 1 + dp[m - i * i]);
dp.push_back(minVal);
}
return dp[n];
}
};
```
JS Code:
```js
/**
* @param {number} n
* @return {number}
*/
var numSquares = function (n) {
if (n <= 0) {
return 0;
}
const dp = Array(n + 1).fill(Number.MAX_VALUE);
dp[0] = 0;
for (let i = 1; i <= n; i++) {
for (let j = 1; j * j <= i; j++) {
// 不选（dp[i]） 还是 选（dp[i - j * j]）
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
};
```
**复杂度分析**
* 时间复杂度：$O(N^2)$
* 空间复杂度：$O(N)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/279.perfect-squares.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.