#279. 完全平方数

dp[n]

dp[x] = Math.min(dp[x], dp[x - square] + 1);

dp[0] = 0;

const dp = new Array(n + 1).fill(Infinity);
dp[0] = 0;

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

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
    // dp[x]：组成 x 所需的完全平方数的最少数量
    // 下标覆盖 0 到 n，因此需要 n + 1 个位置
    // 未计算的状态设为 Infinity，后续才能通过 Math.min 更新为有效答案
    // 不能初始化为 0，否则正数也会被误判为“不需要选择任何数”
    const dp = new Array(n + 1).fill(Infinity);

    // 组成 0 不需要任何数字，也是状态转移的起点
    // 例如 x = 4、square = 4 时，dp[4] 可以由 dp[0] + 1 得到 1
    dp[0] = 0;

    // 当前状态只依赖更小的状态，因此从小到大计算
    // 外层的 x 是当前要凑出的目标值，不是选择的平方数
    for (let x = 1; x <= n; x++) {
        // 枚举最后选择的完全平方数 i²
        // i 是平方根，实际选择的数字是 i * i，即 1、4、9、16……
        // 从 1 开始，保证 x - square < x，依赖的是已经算好的状态
        // 使用 <=，才能包含 x 本身就是平方数的情况；也保证剩余值不为负
        for (let i = 1; i * i <= x; i++) {
            const square = i * i;
            // 选择 square 后，还需要凑出 x - square
            // dp[x - square] 是剩余部分的最少数量，+ 1 表示再选一个 square
            // 剩余部分可以已经包含 square，因此同一个平方数可以重复使用
            // 与已有候选取最小值，而不是直接覆盖，才能保留所有选择中的最优解
            // 例如 x = 12、square = 4：dp[8] + 1 = 2 + 1 = 3
            dp[x] = Math.min(dp[x], dp[x - square] + 1);
        }
        // 所有可能的最后一个平方数都已比较完毕，此时 dp[x] 就是最优答案
    }

    // 返回恰好组成 n 的最少数量；因为可以一直选 1，所以一定有解
    return dp[n];
};

var numSquares = function (n) {
    // dp[x]：使用当前已经枚举过的平方数，恰好组成 x 的最少数量
    // 尚未凑出的目标先设为 Infinity，组成 0 则需要 0 个数
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;

    // 外层逐个引入可选平方数，每种平方数都可以使用任意多次
    for (let i = 1; i * i <= n; i++) {
        const square = i * i;

        // 小于 square 的目标装不下当前平方数，所以从 square 开始
        // 正序遍历，允许在本轮重复使用同一个 square
        // 例如 square = 4：先更新 dp[4]，再用它更新 dp[8]，继而更新 dp[12]
        // 若改为倒序，本轮就无法这样连续使用当前平方数，会变成 0-1 背包
        for (let x = square; x <= n; x++) {
            // dp[x]：保留已有方案；dp[x - square] + 1：再选一个当前平方数
            // 较小目标可能已在本轮更新，所以候选方案允许包含多个 square
            dp[x] = Math.min(dp[x], dp[x - square] + 1);
        }
    }

    // 所有可选平方数都已参与转移，得到目标 n 的最少数量
    return dp[n];
};

var numSquares = function (n) {
    // 队列保存“还需要凑出的剩余值”，起点 n 表示尚未选择任何平方数
    const queue = [n];
    // 同一剩余值只需搜索一次：BFS 第一次到达它时，使用的数字数量已经最少
    const visited = new Array(n + 1).fill(false);
    visited[n] = true;

    // 用 head 读取队首，避免反复 shift 移动数组元素
    let head = 0;
    // steps 表示当前尝试使用的平方数数量，每扩展一层就多选择一个
    let steps = 0;

    while (head < queue.length) {
        // 先固定本层待处理的节点数，新入队的节点留到下一层处理
        // 队列前 head 个元素已处理，因此有效长度是 queue.length - head
        const levelSize = queue.length - head;
        steps++;

        for (let count = 0; count < levelSize; count++) {
            const current = queue[head++];

            // 尝试减去每个不超过当前剩余值的平方数，相当于再选择一个数
            for (let i = 1; i * i <= current; i++) {
                const next = current - i * i;

                // 剩余值为 0，说明已经恰好凑出 n
                // BFS 按使用数量从少到多搜索，第一次找到的就是最少数量
                if (next === 0) {
                    return steps;
                }

                if (!visited[next]) {
                    // 入队时就标记，防止同一层的不同路径重复加入这个剩余值
                    visited[next] = true;
                    queue.push(next);
                }
            }
        }
    }
};