How can I optimize my solution for Perfect Squares?

To optimize Perfect Squares, you can use dynamic programming with a bottom-up approach or BFS for a level-wise search. Consider space and time trade-offs for each method.

What is the time complexity for dynamic programming in Perfect Squares?

The time complexity for dynamic programming is O(n * sqrt(n)) because for each value from 1 to n, you check all perfect squares up to that number.

Can BFS be used to solve the Perfect Squares problem?

Yes, BFS can be used to solve Perfect Squares by treating the problem as a shortest path problem, where each state represents an integer and the goal is to reach 0.

Why does the greedy approach not always work for Perfect Squares?

The greedy approach does not always work because subtracting the largest perfect square at each step may not lead to the minimum number of terms required to sum to n.

What is the base case in dynamic programming for Perfect Squares?

The base case in dynamic programming is dp[0] = 0, since no perfect squares are needed to sum to 0.

#279

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如， 1 、 4 、 9 和 16 都是完全平方数，而 3 和 11 不是。示例 1：输入： n = 12 输出： 3 解释： 12 = 4 +…

数学动态规划广度优先搜索

题目描述

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

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

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 10⁴

lightbulb

解题思路

方法一：动态规划(完全背包)

我们定义 $f[i][j]$ 表示使用数字 $1, 2, \cdots, i$ 的完全平方数组成和为 $j$ 的最少数量。初始时 $f[0][0] = 0$ ，其余位置的值均为正无穷。

我们可以枚举使用的最后一个数字的数量 $k$ ，那么：

f[i][j] = \min(f[i - 1][j], f[i - 1][j - i^2] + 1, \cdots, f[i - 1][j - k \times i^2] + k)

其中 $i^2$ 表示最后一个数字 $i$ 的完全平方数。

不妨令 $j = j - i^2$ ，那么有：

f[i][j - i^2] = \min(f[i - 1][j - i^2], f[i - 1][j - 2 \times i^2] + 1, \cdots, f[i - 1][j - k \times i^2] + k - 1)

将二式代入一式，我们可以得到以下状态转移方程：

f[i][j] = \min(f[i - 1][j], f[i][j - i^2] + 1)

最后答案即为 $f[m][n]$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 为 $sqrt(n)$ 的整数部分。

注意到 $f[i][j]$ 只与 $f[i - 1][j]$ 和 $f[i][j - i^2]$ 有关，因此我们可以将二维数组优化为一维数组，空间复杂度降为 $O(n)$ 。

相似题目：

322. 零钱兑换

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numSquares(self, n: int) -> int:
        m = int(sqrt(n))
        f = [[inf] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 0
        for i in range(1, m + 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if j >= i * i:
                    f[i][j] = min(f[i][j], f[i][j - i * i] + 1)
        return f[m][n]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate identify the optimal approach between dynamic programming and BFS for solving the problem?
question_mark
Does the candidate handle state transitions efficiently in dynamic programming or BFS?
question_mark
How well does the candidate explain the trade-offs between time complexity and space complexity in different approaches?

warning

常见陷阱

外企场景

error
Not considering the correct base case in dynamic programming, such as dp[0] = 0.
error
For BFS, not properly managing the queue, leading to unnecessary computations or missing the shortest path.
error
Assuming that a greedy approach will always yield the optimal solution, which is not guaranteed.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the problem allows negative integers? This would add complexity in handling transitions.
arrow_right_alt
How can this problem be solved with memoization instead of an iterative approach?
arrow_right_alt
What happens if we only use odd perfect squares or squares of primes? This introduces constraints and alters the solution.

help

常见问题

外企场景

继续练习

#264 丑数 II #313 超级丑数 #241 为运算表达式设计优先级