NeetCode #678LC-279Medium1-D Dynamic ProgrammingNC 250
← Back to All Problems#678 · #279 · Perfect Squares(完全平方数)
📌 Problem Statement & Constraints
Given an integer
n, return the fewest number of perfect squares whose sum equals n. A perfect square is k * k for some integer k. Constraints: 1 <= n <= 10^4.💡 Core Algorithmic Approaches
- Let
dp[i]be the minimum number of perfect squares summing toi, withdp[0] = 0. - For each
i, try every squarek * k <= iand relaxdp[i] = min(dp[i], dp[i - k * k] + 1). - This is the unbounded coin-change DP where the coin set is the perfect squares.
- Legendre's three-square theorem gives a constant-time formula, but the DP is the expected interview solution.
💻 Benchmark Python3 Implementation
class Solution:
def numSquares(self, n: int) -> int:
dp = [0] + [float("inf")] * n
for i in range(1, n + 1):
k = 1
while k * k <= i:
dp[i] = min(dp[i], dp[i - k * k] + 1)
k += 1
return dp[n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * sqrt(n)): for each of the n values, up to sqrt(n) squares are tried.
💾 Space Complexity
O(n): the DP array.
⚠️ Interview Pitfalls & Follow-ups
- Subtracting the largest square greedily: for
n = 12greedy gives 9 + 1 + 1 + 1 (4 squares), while 4 + 4 + 4 uses only 3. - Using BFS without a visited set: it re-explores the same remainders and can blow up.
- Initialising
dp[0]to infinity: the base case must be 0. - Ignoring the square 1: it guarantees every
nis reachable, so no unreachable handling is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.