279. 完全平方数

// LeetCode指定调用方法
public int numSquares(int n) {
		
    // 记录结果
    int result = 0;

    // 记录可用平方数
    List<Integer> squareNums = new ArrayList<Integer>();

    // 求可用平方数
    for (int i = 1; i * i <= n; i++) {
        squareNums.add(i * i);
    }

    // 标记该数是否在BFS中扩展过
    boolean[] marks = new boolean[n + 1];

    // 用于BFS的队列
    Queue<Integer> queue = new LinkedList<>();

    // 将第一个数入队
    queue.offer(n);

    // 记录当前队列的长度，当队列为空时，BFS全部搜索结束（用以代替 queue.isEmpty() 增加每次循环判断时的效率）
    int queneLen = 1;

    // BFS
    while (queneLen > 0) {

        // 记录当前扩展轮的数的个数
        int currentQueueLen = queneLen;

        // 更新结果
        result++;

        // 扩展当前轮次的数
        while (currentQueueLen-- > 0) {

            // 将队列中第一个数出队
            int currentNum = queue.poll();

            // 更新当前队列长度
            queneLen--;

            // 遍历平方数，扩展收索
            for (Integer squareNum : squareNums) {

                // 记录扩展后的数
                int nextNum = currentNum - squareNum;

                // 如果扩展数不可用，后面的数也不可以用，此时直接退出循环（根据前面的生成平方数的规则，后面的平方数会越来越大，扩展数则会越来越小）
                if (nextNum < 0) {
                    break;
                }

                // 如果扩展数为0，则BFS结束，返回结果
                if (nextNum == 0) {
                    return result;
                }

                // 如果该数已被扩展过，则跳过该数
                if (marks[nextNum]) {
                    continue;
                }

                // 将扩展数入队
                queue.offer(nextNum);

                // 标记该扩展数已被扩展
                marks[nextNum] = true;

                // 更新当前队列长度
                queneLen++;
            }
        }
    }

    return 0;
}

// LeetCode指定调用方法
public int numSquares(int n) {
		
    // 记录可用平方数
    List<Integer> squareNums = new ArrayList<Integer>();

    // 求可用平方数
    for (int i = 1; i * i <= n; i++) {
        squareNums.add(i * i);
    }

    // 动态规划记录数组，f[j]表示装满背包空间为j的最小物品数
    int[] f = new int[n + 1];

    // 初始化 动态规划记录数组
    Arrays.fill(f, Integer.MAX_VALUE);
    f[0] = 0;

    //  动态规划
    for (Integer squareNum : squareNums) {
        for (int j = squareNum; j <= n; j++) {

            // 状态转移方程
            f[j] = Math.min(f[j], f[j - squareNum] + 1);
        }
    }

    return f[n];
}