225. Perfect Squares
🔗 LeetCode Problem: 279. Perfect Squares
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Math, BFS, DP - Subsequences
Problem Statement
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9
Constraints:
- 1 <= n <= 10^4
🌳 Visual Understanding - Using n = 12
The Problem We're Solving:
Given: n = 12
Goal: Find minimum perfect squares that sum to 12
Perfect squares: Numbers like 1, 4, 9, 16, 25, ...
1² = 1
2² = 4
3² = 9
4² = 16
5² = 25
...
Which perfect squares ≤ 12?
1, 4, 9 (can use these)
16, 25, ... (too large, can't use)
Question: What's the minimum number of perfect squares
that add up to exactly 12? 🤔
Finding All Possible Ways for 12:
Number: 12
Option 1: Use only 1's
━━━━━━━━━━━━━━━━━━━━━━━━━━━
12 = 1+1+1+1+1+1+1+1+1+1+1+1
Count: 12 squares
Option 2: Use 4's and 1's
━━━━━━━━━━━━━━━━━━━━━━━━━━━
12 = 4+4+4
Count: 3 squares ✓ MINIMUM!
Option 3: Use 4's and 1's (different combo)
━━━━━━━━━━━━━━━━━━━━━━━━━━━
12 = 4+4+1+1+1+1
Count: 6 squares
Option 4: Use 9 and 1's
━━━━━━━━━━━━━━━━━━━━━━━━━━━
12 = 9+1+1+1
Count: 4 squares
Option 5: Use 4, 1's
━━━━━━━━━━━━━━━━━━━━━━━━━━━
12 = 4+1+1+1+1+1+1+1+1
Count: 9 squares
All counts: 12, 3, 6, 4, 9
Minimum: 3 (from 4+4+4)
Answer: 3 ✓
Why Greedy FAILS:
CRITICAL UNDERSTANDING:
Greedy approach: Always pick the LARGEST perfect square
Example: n = 12
Step 1: Pick 9 (largest ≤ 12)
Used: [9]
Remaining: 12 - 9 = 3
Step 2: Pick 1 (largest ≤ 3)
Used: [9, 1]
Remaining: 3 - 1 = 2
Step 3: Pick 1 (largest ≤ 2)
Used: [9, 1, 1]
Remaining: 2 - 1 = 1
Step 4: Pick 1 (largest ≤ 1)
Used: [9, 1, 1, 1]
Remaining: 1 - 1 = 0
Greedy result: 9+1+1+1 = 4 squares ✗
But optimal: 4+4+4 = 3 squares ✓
Greedy picks 9 first, but it's better to NOT pick 9!
Picking largest doesn't guarantee minimum count!
This is why we need to try ALL possibilities! 🔑
Another Example - Why Greedy Fails:
n = 6
Greedy:
Pick 4 (largest ≤ 6)
Remaining: 6 - 4 = 2
Pick 1, 1
Total: 4 + 1 + 1 = 3 squares
Optimal:
Pick 1, 1, 4
Total: 1 + 1 + 4 = 3 squares
Same result! But try n = 12 above - greedy fails!
We MUST explore all combinations to find true minimum! 🎯
🧠 The AHA Moment - Why This Problem Is Special
What Makes This Different from Other Problems?
COIN CHANGE (Minimum Coins):
Coins: [1, 2, 5]
Amount: 11
Find: Minimum coins to make 11
Same structure but with coin denominations!
PERFECT SQUARES (This Problem):
"Coins": [1, 4, 9, 16, ...] (perfect squares)
Amount: n
Find: Minimum "coins" to make n
Coins are ALL perfect squares ≤ n!
SAME PATTERN! 🎯
The Key Insight - Try All Squares!
To make n, we can use ANY perfect square s² ≤ n
If we use s² once:
- We've used 1 square
- Need to make (n - s²) with remaining squares
- Remaining takes ??? squares (we need to figure this out!)
- Total: 1 + (squares needed for n - s²)
Try ALL perfect squares s² ≤ n:
For s = 1: 1 + (squares for n - 1)
For s = 2: 1 + (squares for n - 4)
For s = 3: 1 + (squares for n - 9)
...
Pick the one that gives MINIMUM total!
This is the DP insight! 🔑
Building Intuition with Small Example:
n = 5
Perfect squares ≤ 5: 1, 4
Option 1: Use 1 first
5 = 1 + (remaining 4)
How many for 4? → 1 (just use 4)
Total: 1 + 1 = 2 ✓
Option 2: Use 4 first
5 = 4 + (remaining 1)
How many for 1? → 1 (just use 1)
Total: 1 + 1 = 2 ✓
Both give 2! Either 1+4 or 4+1 works!
Minimum: 2 squares
To find "how many for remaining", we solve same problem recursively!
This is the recursive structure! 🎯
🔴 Approach 1: Brute Force (Try All Combinations)
📐 Function Definition
Function Signature:
int numSquares(int n)
What it represents:
Input Parameter n:
- A positive integer
- Example: n = 12
Return Value (int): - Minimum number of perfect squares that sum to n - Example: 3 (because 12 = 4+4+4)
Purpose: - Try all possible combinations of perfect squares - For each square s² ≤ n, try using it and solve remaining - Return the minimum count found
Key Understanding:
For n = 12, we try:
Use 1: 1 + solve(12-1=11)
Use 4: 1 + solve(12-4=8)
Use 9: 1 + solve(12-9=3)
For each choice, recursively solve the remaining!
Pick the choice that gives minimum total!
💡 Intuition
The simplest idea: Try using each perfect square, recursively solve remaining!
Think of it like making change with coins:
You have n = 12 dollars to make
Coins available: 1, 4, 9 (perfect squares ≤ 12)
Cashier thinking:
"Let me try giving 9 dollar coin first"
→ Remaining: 3
→ "Now I need to make 3" (recursive call)
"Or try giving 4 dollar coin first"
→ Remaining: 8
→ "Now I need to make 8" (recursive call)
"Or try giving 1 dollar coin first"
→ Remaining: 11
→ "Now I need to make 11" (recursive call)
Try all options, pick the one using fewest coins!
Same idea for perfect squares! 🎯
📝 Implementation
class Solution {
public int numSquares(int n) {
// Base case
if (n == 0) return 0;
int minCount = Integer.MAX_VALUE;
// Try each perfect square s² ≤ n
for (int s = 1; s * s <= n; s++) {
int square = s * s;
// Use this square once, recursively solve remaining
int count = 1 + numSquares(n - square);
// Track minimum
minCount = Math.min(minCount, count);
}
return minCount;
}
}
🔍 Detailed Dry Run: n = 5
Perfect squares ≤ 5: 1, 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RECURSIVE TREE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
numSquares(5)
│
├─ Try s=1 (square=1): 1 + numSquares(5-1=4)
│ │
│ numSquares(4)
│ ├─ Try s=1 (square=1): 1 + numSquares(4-1=3)
│ │ │
│ │ numSquares(3)
│ │ ├─ Try s=1: 1 + numSquares(2)
│ │ │ numSquares(2)
│ │ │ ├─ Try s=1: 1 + numSquares(1)
│ │ │ │ numSquares(1)
│ │ │ │ └─ Try s=1: 1 + numSquares(0)
│ │ │ │ return 0
│ │ │ │ return 1
│ │ │ return 2
│ │ return 3
│ │
│ └─ Try s=2 (square=4): 1 + numSquares(4-4=0)
│ return 0
│ return 1 ✓
│
│ min(4, 1) = 1
│ return 1
│
│ Result from s=1: 1 + 1 = 2
│
└─ Try s=2 (square=4): 1 + numSquares(5-4=1)
│
numSquares(1)
└─ Try s=1: 1 + numSquares(0)
return 0
return 1
Result from s=2: 1 + 1 = 2
min(2, 2) = 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL RESULT: 2 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
The answer 2 can be achieved by:
5 = 1 + 4 (two squares)
5 = 4 + 1 (two squares)
Why This Is Slow:
Notice the recursion tree:
numSquares(4) is called MULTIPLE times!
numSquares(3) is called MULTIPLE times!
numSquares(2) is called MULTIPLE times!
Lots of repeated work! This is the problem!
For n = 12, the tree would be HUGE!
Many overlapping subproblems being solved over and over!
This is why brute force is TOO SLOW! ❌
📊 Complexity Analysis
Time Complexity: Exponential O(√n^n)
At each level, we branch into √n choices (all squares ≤ n)
Maximum depth is n (worst case using all 1's)
Total: (√n)^n ≈ exponential
For n = 100: Millions of recursive calls!
WAY TOO SLOW! ❌
Space Complexity: O(n)
Recursion stack depth
In worst case (all 1's), depth = n
Why This Is Slow:
❌ Tries every possible combination
❌ Repeats same subproblems many times
❌ Exponential time complexity
✅ But correct and easy to understand!
We need to CACHE the results! → Memoization!
🟡 Approach 2: Memoization (Top-Down DP)
📐 Function Definition
Function Signature:
int numSquares(int n)
What it represents:
Variables we track:
- memo[i] = Minimum squares needed to sum to i
- If memo[i] is computed, reuse it!
- If not computed, compute and cache it!
Purpose: - Same recursive logic as brute force - But CACHE results to avoid recomputation - Each subproblem solved only ONCE!
Key Understanding:
Brute force calls numSquares(4) many times
Memoization calls numSquares(4) ONCE, caches result
Example:
First time numSquares(4) called:
- Compute answer (1)
- Store in memo[4] = 1
Next time numSquares(4) called:
- Check memo[4]
- Found! Return 1 immediately
- No recomputation! ✓
This saves MASSIVE amounts of work!
💡 Intuition
The smart idea: Remember what we've already solved!
Think of it like a cheat sheet while studying:
WITHOUT memoization (brute force):
Question: "How many squares for 4?"
You: *solve from scratch*
Later, same question: "How many squares for 4?"
You: *solve from scratch AGAIN* ❌
WITH memoization:
Question: "How many squares for 4?"
You: *solve from scratch*
You: *write answer in cheat sheet: "4 → 1"*
Later, same question: "How many squares for 4?"
You: *look at cheat sheet*
You: "It's 1!" ✓
You: *instant answer, no recalculation!*
The cheat sheet is the memo array!
📝 Implementation
class Solution {
private Integer[] memo;
public int numSquares(int n) {
memo = new Integer[n + 1];
return helper(n);
}
private int helper(int n) {
// Base case
if (n == 0) return 0;
// Check memo (cheat sheet!)
if (memo[n] != null) {
return memo[n];
}
int minCount = Integer.MAX_VALUE;
// Try each perfect square s² ≤ n
for (int s = 1; s * s <= n; s++) {
int square = s * s;
// Recursive call (might hit memo!)
int count = 1 + helper(n - square);
// Track minimum
minCount = Math.min(minCount, count);
}
// Save to memo before returning!
memo[n] = minCount;
return minCount;
}
}
🔍 Detailed Dry Run: n = 5
memo = [null, null, null, null, null, null]
0 1 2 3 4 5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CALL: helper(5)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
n = 5
memo[5] = null (not computed yet)
Try s=1 (square=1): 1 + helper(5-1=4)
┌─ CALL: helper(4)
│ n = 4
│ memo[4] = null (not computed yet)
│
│ Try s=1 (square=1): 1 + helper(3)
│ ┌─ CALL: helper(3)
│ │ n = 3
│ │ memo[3] = null
│ │
│ │ Try s=1: 1 + helper(2)
│ │ ┌─ CALL: helper(2)
│ │ │ n = 2
│ │ │ memo[2] = null
│ │ │
│ │ │ Try s=1: 1 + helper(1)
│ │ │ ┌─ CALL: helper(1)
│ │ │ │ n = 1
│ │ │ │ memo[1] = null
│ │ │ │
│ │ │ │ Try s=1: 1 + helper(0)
│ │ │ │ return 0
│ │ │ │
│ │ │ │ minCount = 1
│ │ │ │ memo[1] = 1 ✓
│ │ │ └─ return 1
│ │ │
│ │ │ minCount = 1 + 1 = 2
│ │ │ memo[2] = 2 ✓
│ │ └─ return 2
│ │
│ │ minCount = 1 + 2 = 3
│ │ memo[3] = 3 ✓
│ └─ return 3
│
│ After s=1: count = 1 + 3 = 4
│
│ Try s=2 (square=4): 1 + helper(0)
│ return 0
│
│ After s=2: count = 1 + 0 = 1 ✓
│
│ minCount = min(4, 1) = 1
│ memo[4] = 1 ✓
└─ return 1
After s=1: count = 1 + 1 = 2
Try s=2 (square=4): 1 + helper(1)
┌─ CALL: helper(1)
│ n = 1
│ memo[1] = 1 ← FOUND IN MEMO! ✓
└─ return 1 (instant, no recursion!)
After s=2: count = 1 + 1 = 2
minCount = min(2, 2) = 2
memo[5] = 2 ✓
return 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL memo state:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
memo = [0, 1, 2, 3, 1, 2]
0 1 2 3 4 5
Each value computed ONCE and cached! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 2 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Notice: helper(1) was called TWICE
First call: computed and cached
Second call: returned from memo instantly!
This is the power of memoization!
Why This Works:
KEY INSIGHT:
Each unique value n is solved ONCE
Result is cached in memo[n]
Future calls return cached result instantly
Comparison:
Brute force: numSquares(4) computed multiple times
Memoization: numSquares(4) computed ONCE, cached
This transforms exponential → polynomial time!
📊 Complexity Analysis
Time Complexity: O(n × √n)
n unique subproblems (0 to n)
Each subproblem tries √n perfect squares
Each subproblem solved ONCE (cached!)
Total: n × √n
For n = 100: 100 × 10 = 1,000 operations
MUCH better than exponential! ✓
Space Complexity: O(n)
Memo array: O(n)
Recursion stack: O(n) in worst case
Total: O(n)
🟢 Approach 3: Bottom-Up DP (Iterative)
📐 Function Definition
Function Signature:
int numSquares(int n)
What it represents:
DP Array:
- dp[i] = Minimum perfect squares to sum to i
- Build from dp[0], dp[1], ..., up to dp[n]
- Each value uses previous values!
Purpose: - Compute answers for 0, 1, 2, ..., n in order - For each i, try all perfect squares s² ≤ i - Use previously computed dp values!
Key Understanding:
Bottom-up builds from smallest to largest:
dp[0] = 0 (base case)
dp[1]: Try s²=1 → 1 + dp[0] = 1
dp[2]: Try s²=1 → 1 + dp[1] = 2
dp[3]: Try s²=1 → 1 + dp[2] = 3
dp[4]: Try s²=1 → 1 + dp[3] = 4
Try s²=4 → 1 + dp[0] = 1 ✓ (better!)
dp[5]: Try s²=1 → 1 + dp[4] = 2
Try s²=4 → 1 + dp[1] = 2
Build up the solution incrementally!
💡 Intuition
The systematic idea: Build answers from bottom up, like stairs!
Think of it like climbing stairs:
TOP-DOWN (Memoization):
Start at top (n)
Work backwards to bottom (0)
Cache results as you go
BOTTOM-UP (This approach):
Start at bottom (0)
Work upwards to top (n)
Build on previous answers
Like building a house:
You don't start from roof!
You build foundation first (dp[0])
Then first floor (dp[1])
Then second floor (dp[2])
...
Finally reach the top (dp[n])!
Each floor uses the floors below it!
📝 Implementation
class Solution {
public int numSquares(int n) {
// dp[i] = minimum perfect squares to sum to i
int[] dp = new int[n + 1];
// Initialize all to infinity (impossible initially)
Arrays.fill(dp, Integer.MAX_VALUE);
// Base case: need 0 squares to make 0
dp[0] = 0;
// Build up from 1 to n
for (int i = 1; i <= n; i++) {
// Try each perfect square s² ≤ i
for (int s = 1; s * s <= i; s++) {
int square = s * s;
// ═══════════════════════════════════════════════════
// BACKWARD DP: Look at previous value
// ═══════════════════════════════════════════════════
// To make i, use perfect square s² once
// Then need to make i - s² with remaining
// Remaining takes dp[i - square] squares
// Total: 1 + dp[i - square]
dp[i] = Math.min(dp[i], 1 + dp[i - square]);
}
}
return dp[n];
}
}
🔍 Detailed Dry Run: n = 12
Initial state:
dp = [0, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF]
0 1 2 3 4 5 6 7 8 9 10 11 12
Perfect squares ≤ 12: 1, 4, 9
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILD DP TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration: i = 1
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 1: 1
Try s=1 (square=1):
dp[1] = min(INF, 1 + dp[1-1])
= min(INF, 1 + dp[0])
= min(INF, 1 + 0)
= 1 ✓
dp[1] = 1
Iteration: i = 2
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 2: 1
Try s=1 (square=1):
dp[2] = min(INF, 1 + dp[2-1])
= min(INF, 1 + dp[1])
= min(INF, 1 + 1)
= 2 ✓
dp[2] = 2
Iteration: i = 3
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 3: 1
Try s=1 (square=1):
dp[3] = min(INF, 1 + dp[3-1])
= min(INF, 1 + dp[2])
= min(INF, 1 + 2)
= 3 ✓
dp[3] = 3
Iteration: i = 4
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 4: 1, 4
Try s=1 (square=1):
dp[4] = min(INF, 1 + dp[4-1])
= min(INF, 1 + dp[3])
= min(INF, 1 + 3)
= 4
Try s=2 (square=4):
dp[4] = min(4, 1 + dp[4-4])
= min(4, 1 + dp[0])
= min(4, 1 + 0)
= 1 ✓
dp[4] = 1 (using 4 is better!)
Iteration: i = 5
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 5: 1, 4
Try s=1 (square=1):
dp[5] = min(INF, 1 + dp[4])
= min(INF, 1 + 1)
= 2
Try s=2 (square=4):
dp[5] = min(2, 1 + dp[1])
= min(2, 1 + 1)
= 2 ✓
dp[5] = 2
Iteration: i = 6
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 6: 1, 4
Try s=1 (square=1):
dp[6] = min(INF, 1 + dp[5])
= min(INF, 1 + 2)
= 3
Try s=2 (square=4):
dp[6] = min(3, 1 + dp[2])
= min(3, 1 + 2)
= 3 ✓
dp[6] = 3
Iteration: i = 7
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 7: 1, 4
Try s=1:
dp[7] = min(INF, 1 + dp[6])
= min(INF, 1 + 3)
= 4
Try s=2:
dp[7] = min(4, 1 + dp[3])
= min(4, 1 + 3)
= 4 ✓
dp[7] = 4
Iteration: i = 8
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 8: 1, 4
Try s=1:
dp[8] = min(INF, 1 + dp[7])
= min(INF, 1 + 4)
= 5
Try s=2:
dp[8] = min(5, 1 + dp[4])
= min(5, 1 + 1)
= 2 ✓
dp[8] = 2 (use 4+4)
Iteration: i = 9
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 9: 1, 4, 9
Try s=1:
dp[9] = min(INF, 1 + dp[8])
= min(INF, 1 + 2)
= 3
Try s=2:
dp[9] = min(3, 1 + dp[5])
= min(3, 1 + 2)
= 3
Try s=3 (square=9):
dp[9] = min(3, 1 + dp[0])
= min(3, 1 + 0)
= 1 ✓
dp[9] = 1 (just use 9!)
Iteration: i = 10
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 10: 1, 4, 9
Try s=1:
dp[10] = min(INF, 1 + dp[9])
= min(INF, 1 + 1)
= 2 ✓
Try s=2:
dp[10] = min(2, 1 + dp[6])
= min(2, 1 + 3)
= 2
Try s=3:
dp[10] = min(2, 1 + dp[1])
= min(2, 1 + 1)
= 2 ✓
dp[10] = 2 (use 9+1)
Iteration: i = 11
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 11: 1, 4, 9
Try s=1:
dp[11] = min(INF, 1 + dp[10])
= min(INF, 1 + 2)
= 3 ✓
Try s=2:
dp[11] = min(3, 1 + dp[7])
= min(3, 1 + 4)
= 3
Try s=3:
dp[11] = min(3, 1 + dp[2])
= min(3, 1 + 2)
= 3 ✓
dp[11] = 3 (use 9+1+1)
Iteration: i = 12 - FINAL
━━━━━━━━━━━━━━━━━━━━
Perfect squares ≤ 12: 1, 4, 9
Try s=1 (square=1):
dp[12] = min(INF, 1 + dp[11])
= min(INF, 1 + 3)
= 4
Try s=2 (square=4):
dp[12] = min(4, 1 + dp[8])
= min(4, 1 + 2)
= 3 ✓
Try s=3 (square=9):
dp[12] = min(3, 1 + dp[3])
= min(3, 1 + 3)
= 3
dp[12] = 3 (using 4+4+4 or other combinations)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL DP ARRAY:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp = [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
0 1 2 3 4 5 6 7 8 9 10 11 12
Verification:
dp[0] = 0 (base)
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[7] = 4 (4+1+1+1)
dp[8] = 2 (4+4)
dp[9] = 1 (9)
dp[10] = 2 (9+1)
dp[11] = 3 (9+1+1)
dp[12] = 3 (4+4+4) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ANSWER: 3 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why This Works - Visual Understanding:
Think of it like Fibonacci:
Fibonacci:
fib[0] = 0
fib[1] = 1
fib[n] = fib[n-1] + fib[n-2]
Compute fib[2], fib[3], ..., in order
Each uses previous values!
Perfect Squares:
dp[0] = 0
dp[i] = min(1 + dp[i-s²]) for all s² ≤ i
Compute dp[1], dp[2], ..., in order
Each uses previous values!
SAME PATTERN - Build from bottom up! 🎯
📊 Complexity Analysis
Time Complexity: O(n × √n)
Outer loop: n iterations (1 to n)
Inner loop: √n perfect squares to try
Total: n × √n
For n = 10,000:
10,000 × 100 = 1,000,000 operations
Very manageable! ✓
Space Complexity: O(n)
DP array of size n+1
No recursion stack needed
Total: O(n)
📊 Approach Comparison
┌──────────────────────────────────────────────────────────────┐
│ PERFECT SQUARES - APPROACH COMPARISON │
├──────────────┬───────────┬───────────┬────────────┬──────────┤
│ Approach │ Time │ Space │ Clarity │Interview │
├──────────────┼───────────┼───────────┼────────────┼──────────┤
│ Brute Force │ Exp │ O(n) │ High │ Start │
│ Memoization │ O(n√n) │ O(n) │ Good │ Good │
│ Bottom-Up DP │ O(n√n) │ O(n) │ Best ✓ │ Best ✓ │
└──────────────┴───────────┴───────────┴────────────┴──────────┘
For interviews: Show progression from brute force to DP!
💻 Complete Working Code
class Solution {
public int maxProduct(int[] nums) {
return dp(nums);
}
// Approach 3: Bottom-Up DP - O(n√n) time, O(n) space
private int dp(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int s = 1; s * s <= i; s++) {
int square = s * s;
dp[i] = Math.min(dp[i], 1 + dp[i - square]);
}
}
return dp[n];
}
// Approach 2: Memoization - O(n√n) time, O(n) space
private Integer[] memo;
private int memoization(int n) {
if (memo == null) {
memo = new Integer[n + 1];
}
return helper(n);
}
private int helper(int n) {
if (n == 0) return 0;
if (memo[n] != null) return memo[n];
int minCount = Integer.MAX_VALUE;
for (int s = 1; s * s <= n; s++) {
int square = s * s;
int count = 1 + helper(n - square);
minCount = Math.min(minCount, count);
}
memo[n] = minCount;
return minCount;
}
// Approach 1: Brute Force - Exponential time
private int bruteForce(int n) {
if (n == 0) return 0;
int minCount = Integer.MAX_VALUE;
for (int s = 1; s * s <= n; s++) {
int square = s * s;
int count = 1 + bruteForce(n - square);
minCount = Math.min(minCount, count);
}
return minCount;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.numSquares(12) == 3);
System.out.println(s.numSquares(13) == 2);
}
}
🔑 Key Insights
Why Greedy Fails:
Picking largest square first doesn't work!
Example: n = 12
Greedy: 9+1+1+1 = 4 squares ✗
Optimal: 4+4+4 = 3 squares ✓
Must try ALL combinations to find minimum!
Pattern Recognition:
This is EXACTLY like Coin Change!
Coin Change:
Coins: [1, 2, 5]
Amount: 11
dp[i] = min coins to make i
Perfect Squares:
"Coins": [1, 4, 9, 16, ...]
Amount: n
dp[i] = min squares to make i
SAME PATTERN - Unbounded Knapsack! 🔑
Why DP Works:
For each i, try using every perfect square s²:
dp[i] = min(1 + dp[i - s²])
Build from dp[0] to dp[n]
Each value uses previous values
Classic bottom-up DP!
🎪 Memory Aid
"Try ALL squares, pick minimum!"
"Build from 0 to n, use previous values!"
"Like Fibonacci but with √n choices!"
"Same as Coin Change - Unbounded Knapsack!" ✨
⚠️ Common Mistakes
- ❌ Using greedy (always picking largest square)
- ❌ Forgetting base case dp[0] = 0
- ❌ Wrong loop condition (s <= i instead of s*s <= i)
- ❌ Not initializing dp array with infinity
- ❌ Forgetting to try ALL perfect squares
✅ Interview Talking Points
"This is a variation of Coin Change problem.
Why greedy fails:
Example n=12: Greedy picks 9 first → 4 squares
But optimal is 4+4+4 → 3 squares
Must try all combinations!
DP Approach:
dp[i] = minimum squares to sum to i
Base case: dp[0] = 0
For each i from 1 to n:
Try every perfect square s² ≤ i
dp[i] = min(1 + dp[i - s²])
This is Unbounded Knapsack pattern!
Complexity: O(n√n) time, O(n) space
- Try n values
- Each tries √n perfect squares
- Optimal solution!"
📝 Quick Revision Notes
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public int numSquares(int n) {
// int res = recursive(n);
// Integer[] memo = new Integer[n + 1];
// int res = topDown(n, memo);
int res = bottomUp(n);
// if nothing works out, infinite returns back. Need to return 0 in that case.
return res == Integer.MAX_VALUE ? 0 : res;
}
private int bottomUp(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
// base case
dp[0] = 0;
for (int i = 1; i <= n; i++) {
// below is exactly same loop as top down.
// Only difference is that in bottom up, we will calculate for every number in
// outer for loop.
for (int j = 1, square = 1; square <= i; j++, square = j * j) {
int temp = dp[i - square];
dp[i] = Math.min(dp[i], 1 + temp);
}
}
return dp[n];
}
private int topDown(int n, Integer[] memo) {
if (n == 0) {
return 0;
}
if (n < 0) {
return Integer.MAX_VALUE;
}
if (memo[n] != null) {
return memo[n];
}
int res = Integer.MAX_VALUE;
// step 2: Start trying fron 1 to n.
for (int i = 1, square = 1; square <= n; i++, square = i * i) {
// step 3: Lets say i = 1 tried. Try for remaining.
int temp = topDown(n - square, memo);
if (temp != Integer.MAX_VALUE) {
res = Math.min(res, 1 + temp);
}
}
return memo[n] = res;
}
private int recursive(int n) {
// step 1: base case 1.
// why 0 for 0?
// for example, if n = 4 comes here, no more number required.
if (n == 0) {
return 0;
}
// step 4: do not consider for -ve value.
if (n < 0) {
return Integer.MAX_VALUE;
}
int res = Integer.MAX_VALUE;
// step 2: Start trying fron 1 to n.
for (int i = 1; i <= n; i++) {
// step 3: Lets say i = 1 tried. Try for remaining.
int temp = recursive(n - i * i);
if (temp != Integer.MAX_VALUE) {
res = Math.min(res, 1 + temp);
}
}
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.numSquares(12) == 3);
System.out.println(s.numSquares(13) == 2);
System.out.println(s.numSquares(10000));
}
}
🎉 Congratulations!
You've mastered Perfect Squares - a classic DP problem!
What You Learned:
✅ Why greedy fails - Must try all combinations
✅ Brute force approach - Try every square recursively
✅ Memoization - Cache results to avoid recomputation
✅ Bottom-up DP - Build from 0 to n systematically
✅ Pattern recognition - Same as Coin Change!
✅ O(n√n) solution - Efficient and optimal
You've mastered Unbounded Knapsack pattern! 🚀✨