LeetCode 279. 完全平方数

279. 完全平方数

解题思路

参考代码

与零钱兑换思路一致

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n + 1);
        dp[0] = 0;

        for(int i = 1; i <= n; i ++) {
            int temp = dp[i];
            // 遍历所有 ≤ i 的完全平方数
            for(int j = 1; j * j <= i; j ++) {
                int square = j * j;
                // 凑i的最少个数
                temp = Math.min(temp, dp[i - square] + 1);
            }
            dp[i] = temp;
        }
        return dp[n];
    }
}

BFS 解法(超时)

class Solution {
    public int numSquares(int n) {
        List<Integer> squares = new ArrayList<>();
        for(int i = 1; i * i <= n; i ++) {
            squares.add(i * i);
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{n, 0});

        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            int curNum = current[0];
            int level = current[1];

            for(int s : squares) {
                if(curNum - s == 0) {
                    return level + 1;
                }
                if(curNum - s > 0) {
                    queue.offer(new int[]{curNum - s, level + 1});
                }
            }
        }
        return n;
    }
}