Back to Problem
Official
932 views
Editorial: Perfect Squares
by admin ·
9
1 Intuition
Like coin change where the coins are the squares.
2 Approach
dp[i] = 1 + min(dp[i - s]) over squares s ≤ i.
3 Complexity Analysis
Time O(n·√n), Space O(n).
4 Solution Code
class Solution:
def numSquares(self, n: int) -> int:
dp = [0] + [n] * n
for i in range(1, n + 1):
j = 1
while j * j <= i:
dp[i] = min(dp[i], dp[i - j * j] + 1)
j += 1
return dp[n]5 Code Walkthrough
The reference solution below implements the approach step by step.