Ricky.L的随笔
0%

LeetCode.279.完全平方数（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.279.完全平方数（中等）

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

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

题解

解法1：动态规划

给定一个目标，有一组选择，做出选择，得出最优的结果，就是背包问题。
完全平方数没有限定选择个数，所以是完全背包问题。

设dp[i]表示和为i的完全平方数的最少数量。
对于每个dp[i]求解，从小到大穷举所有可选的完全平方数做出一次选择，挑选一个使用平方数数量最少的。

状态转移方程
dp[i] = minOf(dp[i], 1 + dp[i - j * j] + 1，其中1 <= j <= i。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    fun numSquares(n: Int): Int {
        // dp[i]表示和为i的完全平方数的最少数量
        // dp[0]没意义
        val dp = IntArray(n + 1) { 0 }
        for (i in 1..n) {
            // dp[i]最多数量就是全部1相加，当做默认值，看有没有小的
            dp[i] = i
            var j = 1
            while (j * j <= i) {
                dp[i] = minOf(dp[i], 1 + dp[i - j * j])
                j++
            }
        }
        return dp[n]
    }
}

时间复杂度：$O(n *\sqrt{n})$
空间复杂度：$O(n)$

解法2：bfs

如果先用递归求解，画出递归树就很好想象了。
可以进行层序遍历一层一层的算。
第一层依次减去一个平方数得到第二层；
第二层依次减去一个平方数得到第三层；
每递进一层，使用过的平方数个数加1；
当某一层出现了0，当前层数就是答案。

注意点
因为会有重叠子问题，所以要避免重复纳入已经计算过的节点，用visited数组记录访问过的节点。

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
import java.util.*

class Solution {
    fun numSquares(n: Int): Int {
        val queue = ArrayDeque<Int>()
        val visited = mutableSetOf<Int>()
        queue.add(n)
        var level = 0
        while (queue.isNotEmpty()) {
            level++
            val size = queue.size
            repeat(size) {
                val num = queue.poll()
                visited.add(num)

                var j = 1
                while (j * j <= num) {
                    val small = num - j * j
                    if (small == 0) return level
                    if (!visited.contains(small)) {
                        queue.add(small)
                    }
                    j++
                }
            }
        }
        return -1
    }
}