完全平方数-279

[sl1673495]

给定正整数  n，找到若干个完全平方数（比如  1, 4, 9, 16, ...）使得它们的和等于
n。你需要让组成和的完全平方数的个数最少。

示例  1:

输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2:

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/perfect-squares 著
作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这个问题完全可以转化成 DP 问题。

对于求 f(12)来说，可以转化为求 f(12 - 任意一个平方数) + 1。

这个 + 1 是由于我们选出了一个平方数，所以也会算作凑目标值的次数。

那么假设这个平方数是 n，就在求解 12 的这一次循环里，不断的从 1 开始递增这个平方
数 1、2、4、8 .... 直到 12 - n < 0 中断，在这个过程中去找到能凑成 12 的最小的次
数。由于动态规划是自底向上的，f(12 - n) 是已经求好的值，那么结果就很容易得出了。

题解

/**
 * @param {number} n
 * @return {number}
 */
let numSquares = function(n) {
  let dp = []

  // 求0就假设为0次
  dp[0] = 0

  for (let i = 1; i <= n; i++) {
    let j = 1
    // 初始化为Infinity 这样后面任意一个小值都可以覆盖它
    let min = Infinity
    while (true) {
      // 用 i 减去不断递增的平方数 j * j
      let prev = i - j * j
      if (prev < 0) {
        break
      }

      // 假设i = 10、j = 1 实际上就是在求dp[10 - 1] + 1
      // 也就是凑成 9 的最小次数 再加上 1（也就是 1 这个平方数的次数）
      min = Math.min(min, dp[prev] + 1)
      j++
    }
    dp[i] = min === Infinity ? 0 : min
  }

  return dp[n]
}

[A-tongmu]

不断的从 1 开始递增这个平方
数 1、2、4、8 .... 直到 12 - n < 0 中断
这个平方数是1、4、9、16...吧