【Leetcode】279.完全平方数

279.完全平方数

题目

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

即：要用最少的完全平方数组成n，求这个最少的完全平方数的个数为多少。

示例 1:
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

方法1（动态规划）

  • 状态定义：dp[i]表示组成数字i要用的最少完全平方数个数
  • base case：dp[0] = 0, dp[1] = 1
  • 状态转移方程：$dp[i] = min(dp[i], dp[i - jj] + 1)$
    最开始初始化dp[i]都为i，即用i个1（1也是完全平方数）可以组成i。
    j    j为完全平方数，状态转移方程的意思为：整数i-j * j最少要用dp[i - j * j]个完全平方数组成，那么算上这个完全平方数的话，整数i可以用dp[i - j * j] + 1个完全平方数组成，于是将dp[i - j * j] + 1与原来的dp[i]取较小的那个，便可得到整数i最少可用多少个完全平方数组成。

代码

1
2
3
4
5
6
7
8
9
10
11
public int numSquares(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2; i <= n; i++){
        dp[i] = i;
        for(int j = 1; i - j * j >= 0; j++)
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
    return dp[n];
}

方法2（BFS）

把0到n的每个整数看成图中的一个节点，如果两个整数之间相差一个平方数，那么就认为这两个整数所在的节点间有一条边。

所以题目要求的最小的平方数数量，也就是求解从节点 n 到节点 0 的最短路径。

在图中的最短路径问题，很容易想到BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int numSquares(int n) {
    if(n <= 0)
        return 0;
    boolean[] visited = new boolean[n + 1];
    Queue<Integer> queue = new LinkedList<>();
    List<Integer> squares = generateNum(n);
    queue.add(n);
    visited[n] = true;
    int count = 0;
    while(!queue.isEmpty()){
        int size = queue.size();
        count++;
        for(int i = 0; i < size; i++){
            int temp = queue.poll();
            for(int square : squares){
                if(temp - square == 0)
                    return count;
                if(temp - square < 0)
                    break;
                if(visited[temp - square])
                    continue;
                queue.add(temp - square);
                visited[temp - square] = true;
            }
        }
    }
    return count;
}

//生成小于n的所有完全平方数
public List<Integer> generateNum(int n){
    List<Integer> nums = new LinkedList<>();
    for(int i = 1; i * i <= n; i++){
        nums.add(i * i);
    }
    return nums;
}