NUHMAN.com

Introduction

LeetCode 279: Perfect Squares is a classic dynamic programming and number theory problem. Given a number n, your task is to find the minimum number of perfect square numbers (like 1, 4, 9, 16, ...) that sum up to n.

This problem closely mirrors the Coin Change problem, where each perfect square is like a "coin denomination."

Problem Statement

Given an integer n, return the least number of perfect square numbers that sum to n.

Examples

python

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9

✅ Step-by-Step Solution

🔍 Step 1: Understand the Perfect Squares

For a number n, the perfect squares ≤ n are:

• 1^2 = 1
• 2^2 = 4
• 3^2 = 9
• ...
• ⌊√n⌋^2

We can use these to form the sum that makes n.

🧠 Step 2: Dynamic Programming Approach

We'll use a bottom-up DP array:

• Let dp[i] be the minimum number of perfect squares that sum to i
• Initialize dp[0] = 0 (zero sum needs zero squares)
• For each number i from 1 to n, and for each square j*j ≤ i:

python

dp[i] = min(dp[i], dp[i - j*j] + 1)

This checks every square we can subtract and adds 1 to the count.

✅ Python Code (DP)

python

import math

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for i in range(1, n + 1):
            for j in range(1, int(math.isqrt(i)) + 1):
                dp[i] = min(dp[i], dp[i - j*j] + 1)
        
        return dp[n]

🧪 Dry Run (n = 12)

• dp[1] = 1 (1)
• dp[2] = 2 (1+1)
• dp[3] = 3 (1+1+1)
• dp[4] = 1 (4)
• dp[5] = 2 (4+1)
• dp[6] = 3 (4+1+1)
• dp[12] = min(dp[12 - 1], dp[12 - 4], dp[12 - 9]) + 1 = min(3, 3, 3) + 1 = 4
• But wait!
• Try 4+4+4 = 3 squares → dp[12] = 3 ✅

🌀 Optional: BFS Approach

A BFS treats this as a shortest-path problem:

• Each node is a number from n down to 0
• Each edge is a subtraction of a perfect square

It's a bit more involved but can be more efficient in some scenarios.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n√n)Space ComplexityO(n)

🔍 Edge Cases

• n = 1 → 1
• n = 2 → 2 (1+1)
• n = 0 → 0
• n = 10000 → Efficient DP/BFS needed

✅ Conclusion

LeetCode 279: Perfect Squares is an essential DP problem that blends:

• Classical Coin Change-style logic
• Mathematical intuition of perfect squares
• Optimization via bottom-up DP