Skip to main content

完全平方数

Tips

题目类型: Dynamic Programming

背包问题汇总

题目​

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

完全平方数是一个整数, 其值等于另一个整数的平方; 换句话说, 其值等于一个整数自乘的. 例如: 1, 4, 9 和 16 都是完全平方数, 而 3 和 11 不是.

提示:
  • 1 <= n <= 10⁴
示例
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4
输入: n = 13
输出: 2
解释: 13 = 4 + 9

题解​

翻译一下就是: 完全平方数就是物品(可以无限件使用), 凑个正整数 n 就是背包, 问凑满这个背包最少有多少物品.

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  const dp = new Array(n + 1).fill(Infinity)
  dp[0] = 0 // 和为 0 的完全平方数数量为 0

  for (let i = 1; i <= n; i++) {
    for (let w = i * i; w <= n; w++) {
      dp[w] = Math.min(dp[w], dp[w - i * i] + 1)
    }
  }

  return dp[n]
}