/**
 * @param {number} n
 * @return {number}
 */

const memo = Array.from({ length: 101 }, () => Array(10001).fill(-1)) // -1 表示没有计算过

function dfs(i, j) {
  // 递归终止条件 1：没有可用的平方数（i=0）
  if (i === 0) {
    // 如果目标和 j 也为 0，说明刚好凑成，需要 0 个；否则无法凑成，返回无穷大
    return j === 0 ? 0 : Infinity
  }

  // 记忆化优化：如果该状态已经计算过，直接返回结果，避免重复递归
  if (memo[i][j] !== -1) {
    return memo[i][j]
  }

  // 核心逻辑：分两种情况讨论
  // 情况 1：目标和 j 小于 i²，无法选第 i 个平方数，只能不选
  if (j < i * i) {
    memo[i][j] = dfs(i - 1, j) // 存储结果到记忆数组
  }
  // 情况 2：目标和 j 大于等于 i²，可以选或不选，取最小值
  else {
    // 不选第 i 个平方数：dfs(i-1, j)
    // 选第 i 个平方数：dfs(i, j - i*i) + 1（选了一个，个数+1）
    // Math.min 取两者最小值，即为当前状态的最优解
    memo[i][j] = Math.min(dfs(i - 1, j), dfs(i, j - i * i) + 1)
  }

  // 返回当前状态的计算结果
  return memo[i][j]
}

/**
 * 主函数：计算组成 n 的完全平方数的最少个数
 * @param {number} n - 目标正整数
 * @returns {number} - 最少个数
 */
const numSquares = function (n) {
  // 调用递归函数：
  //   - 第一个参数：Math.floor(Math.sqrt(n)) 表示最大的可用平方数底数（比如 n=10，最大是 3²=9）
  //   - 第二个参数：n 表示目标和
  return dfs(Math.floor(Math.sqrt(n)), n)
}