#279. Perfect Squares

https://leetcode.com/problems/perfect-squares/description/?envType=daily-question&envId=2024-02-08

function numSquares(n) {
    // Initialize an array to store the least number of perfect squares that sum to each index
    const dp = new Array(n + 1).fill(Number.MAX_SAFE_INTEGER);
    dp[0] = 0; // Base case: zero requires 0 perfect squares

    // Iterate through each number up to n
    for (let i = 1; i <= n; i++) {
        // Iterate through perfect squares less than or equal to the current number
        for (let j = 1; j * j <= i; j++) {
            // Update dp[i] if the current perfect square improves the result
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }

    return dp[n];
}

It still shocks how dynamic programming solves these kinds of questions.

Got help from ChatGPT on this one.