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.

Solution(javascript)

/** 可以转成背包问题
 * @param {number} n
 * @return {number}
 */
// const numSquares = (n) => {
//   const maxLength = Math.ceil(Math.sqrt(n))
//   const squareLengths = new Array(maxLength).fill(0).map((v, index) => index + 1)
//   const memo = {}
//   const aux = (sum) => {
//     if (memo[sum] !== undefined) {
//       return memo[sum]
//     }
//     if (sum === n) {
//       return 0
//     }
//     if (sum > n) {
//       return Infinity
//     }
//     memo[sum] = Math.min(...squareLengths.map(length => aux(sum + length * length) + 1))
//     return memo[sum]
//   }
//   return aux(0)
// }

const numSquares = (n) => {
  const maxLength = Math.ceil(Math.sqrt(n))
  const squareLengths = new Array(maxLength).fill(0).map((v, index) => (index + 1) ** 2)
  const memo = {}
  const aux = (index, sum) => {
    memo[index] = memo[index] || {}
    if (memo[index][sum] !== undefined) {
      return memo[index][sum]
    }
    if (sum === n) {
      return 0
    }
    if (sum > n || index > squareLengths.length - 1) {
      return Infinity
    }
    memo[index][sum] = Math.min(
      aux(index, sum + squareLengths[index]) + 1,
      aux(index + 1, sum),
    )
    return memo[index][sum]
  }
  return aux(0, 0)
}