完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。

你需要让组成和**的**完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：1 <= n <= 104

完全背包

1. 题意分析：
   1. 观察题目发现，我们可以使用不限个数的完全平方数，所以可以使用完全背包方法。
2. 定义状态：
   1. dp[i] ：凑成数 **i** 需要的最少的完全平方数的个数
3. 四平方和定理（每个最多由4个完全平方数的和构成）
   1. 随着时间的推移，已经提出并证明的数学定理可以解决这个问题。在这一节中，我们将把这个问题分成几个例子。
   2. 1770 年，Joseph Louis Lagrange 证明了一个定理，称为四平方和定理，也称为 Bachet 猜想，它指出每个自然数都可以表示为四个整数平方和：
      1. 
   3. 其中_a_0,_a_1,_a_2,_a_3, 表示整数
   4. 所以dp[i]可以直接初始化为4（最多的情况，之后再逐个检查）
4. 
   

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  let dp = new Array(n + 1).fill(4);
  // dp[i] ：凑成数 i 需要的最少的完全平方数的个数
  dp[0] = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      // i就等于j*j加上某个数，所以所需完全平方数的个数要加1
      //                           i = j*j+ ?
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
};