279.perfect-squares.md

## 题目地址
https://leetcode.com/problems/perfect-squares/description/

## 题目描述


```
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.
Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

```

## 思路

直接递归处理即可，但是这种暴力的解法很容易超时。如果你把递归的过程化成一棵树的话（其实就是递归树），
可以看出中间有很多重复的计算。 

如果能将重复的计算缓存下来，说不定能够解决时间复杂度太高的问题。

> 递归对内存的要求也很高， 如果数字非常大，也会面临爆栈的风险，将递归转化为循环可以解决。

如果使用DP，其实本质上和递归 + 缓存 差不多。

## 关键点解析

- 如果用递归 + 缓存， 缓存的设计很重要
我的做法是key就是n，value是以n为起点，到达底端的深度。
下次取出缓存的时候用当前的level + 存的深度 就是我们想要的level.

## 代码

```js
/*
 * @lc app=leetcode id=279 lang=javascript
 *
 * [279] Perfect Squares
 *
 * https://leetcode.com/problems/perfect-squares/description/
 *
 * algorithms
 * Medium (40.98%)
 * Total Accepted:    168.2K
 * Total Submissions: 408.5K
 * Testcase Example:  '12'
 *
 * Given a positive integer n, find the least number of perfect square numbers
 * (for example, 1, 4, 9, 16, ...) which sum to n.
 *
 * Example 1:
 *
 *
 * Input: n = 12
 * Output: 3
 * Explanation: 12 = 4 + 4 + 4.
 *
 * Example 2:
 *
 *
 * Input: n = 13
 * Output: 2
 * Explanation: 13 = 4 + 9.
 */

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);
};
```