Perfect Squares

Problem Summary

Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of another integer (for example, 1, 4, 9, and 16 are perfect squares). The value of n is between 1 and 10,000.

Techniques

Math
Dynamic Programming
Breadth-First Search

Solution

function knapsackUnboundMinimizeGenerated(values: number[], capacity: number) {
    const dp = Array(capacity + 1).fill(Infinity)
    dp[0] = 0

    for (const value of values) {
        for (let i = value; i <= capacity; i++) {
            dp[i] = Math.min(dp[i], 1 + dp[i - value])
        }
    }

    return dp[capacity] === Infinity ? -1 : dp[capacity]
}

function numSquares(n: number): number {
    const generatedSquares = []

    for (let i = 1; i * i <= n; i++) {
        generatedSquares.push(i * i)
    }

    return knapsackUnboundMinimizeGenerated(generatedSquares, n)
};